論文の概要: Tight Bounds on the Randomized Communication Complexity of Vector-in-Subspace

• arxiv url: http://arxiv.org/abs/2610.30052v1
• Date: Wed, 21 Oct 2026 17:12:19 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-23 00:40:06.455231
• Title: Tight Bounds on the Randomized Communication Complexity of Vector-in-Subspace
• Title（参考訳）: ベクトル・イン・サブスペースのランダム化通信複雑性に関するタイト境界
• Abstract要約: 我々は、最大で1/3$の誤差を持つ$mathbb Rn$におけるベクトル-in-Subspaceのランダム化通信複雑性が$(sqrt n)$であることを証明する。 正確なワンウェイ量子プロトコルは$O(log n)$ qubitsを使用しており、対話型古典通信よりも指数的量子優位性の幾何学的な例である。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We prove that the randomized communication complexity of Vector-in-Subspace in $\mathbb R^n$ with error at most $1/3$ is $Θ(\sqrt n)$. Alice holds a unit vector $u$ and Bob holds an $n/2$-dimensional subspace $H$; they must distinguish $u\in H$ from $u\in H^\perp$. An exact one-way quantum protocol uses $O(\log n)$ qubits, making the problem a geometric example of an exponential quantum advantage over interactive classical communication. Our lower bound matches Raz's $O(\sqrt n)$ upper bound, improves the $Ω(n^{1/3})$ lower bound of Klartag and Regev, and removes the total-rank restriction in Grupel's $Ω(\sqrt n)$ result. The proof establishes a Gaussian moment bound over complete rectangle partitions. A complex Gaussian representation yields a vanishing even moment whose cancellation is preserved when averaging over the partition. We control the signed conditional moments around a real center by decomposing conditional Gaussian measures into fixed coordinates and sub-Gaussian components. Combining this estimate with spherical harmonic analysis gives the communication lower bound.
• Abstract（参考訳）: 誤りの最大値が1/3$であるような$\mathbb R^n$におけるベクトル-in-Subspaceのランダム化通信複雑性は、$(\sqrt n)$であることを示す。 アリスは単位ベクトル$u$を持ち、ボブは$n/2$-次元部分空間$H$を持ち、それらは$u\in H^\perp$と$u\in H^\perp$を区別しなければならない。 正確な片方向量子プロトコルは$O(\log n)$ qubitsを使用しており、対話型古典通信よりも指数的量子優位性の幾何学的な例である。 我々の下界はRazの$O(\sqrt n)$上界と一致し、Klartag と Regev の $Ω(n^{1/3})$下界を改善し、Grupel の $Ω(\sqrt n)$ の結果の総ランク制限を取り除く。 この証明は、完全矩形分割上のガウスモーメントを確立する。 複素ガウス表現は、分割を平均化するときにキャンセルが保存される消滅する偶数モーメントを与える。 我々は、条件ガウス測度を固定座標と準ガウス成分に分解することで、実中心付近の符号付き条件モーメントを制御する。 この推定と球面調和解析を組み合わせることで、通信の低境界が得られる。

関連論文リスト

• Geometry-Dependent Bounds for Online Non-Monotone DR-Submodular Maximization [55.29259818039367]
  凸閉集合上の逆オンライン非負の非単調DR-部分モジュラ函数について検討する。 学習者は、目的を観察する前に各アクションを学習し、後から最高の固定アクションと競合する。 定数対物列は、最適に多くの1次クエリでオフラインの$(4/9-varepsilon)$近似を生成する。
  論文  参考訳（メタデータ） (2026-09-30T18:26:29Z)
• Exponential lower bounds for low-degree strategies in position-based quantum cryptography [0.764671395172401]
  非局所量子計算 (NLQC) は、2つの遠隔操作者による2部単位のU_AB$の実装に基づいている。 ユニタリな$U_AB$が存在するかどうかを知ることは、大きなオープンな問題である。 このような指数的下界は、位置ベースの量子暗号のセキュリティに不可欠である。
  論文  参考訳（メタデータ） (2026-09-28T16:43:48Z)
• The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
  この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。 アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
  論文  参考訳（メタデータ） (2024-10-26T06:21:42Z)
• Measuring quantum relative entropy with finite-size effect [53.64687146666141]
  相対エントロピー$D(rho|sigma)$を$sigma$が知られているときに推定する。 我々の推定器は次元$d$が固定されたときにCram'er-Rao型境界に達する。
  論文  参考訳（メタデータ） (2024-06-25T06:07:20Z)
• Interplay between depth and width for interpolation in neural ODEs [0.0]
  それらの幅$p$と層遷移数$L$の相互作用について検討する。 高次元設定では、$p=O(N)$ニューロンが正確な制御を達成するのに十分であることを示す。
  論文  参考訳（メタデータ） (2024-01-18T11:32:50Z)
• Threshold Phenomena in Learning Halfspaces with Massart Noise [56.01192577666607]
  ガウス境界の下でのマスアートノイズ付きmathbbRd$におけるPAC学習ハーフスペースの問題について検討する。 この結果は,Massartモデルにおける学習ハーフスペースの複雑さを定性的に特徴づけるものである。
  論文  参考訳（メタデータ） (2021-08-19T16:16:48Z)
• $k$-Forrelation Optimally Separates Quantum and Classical Query Complexity [3.4984289152418753]
  我々は、$N$ビット上の任意の部分関数は、$q$量子クエリを作れば、ランダムな推測よりも$delta$で計算できることを示した。 我々はまた、$k$-Forrelation問題 -- $q = lceil k/2 rceil$量子クエリで計算できる部分関数 -- を予想した。
  論文  参考訳（メタデータ） (2020-08-16T21:26:46Z)
• Quantum Distributed Complexity of Set Disjointness on a Line [3.2590610391507444]
  Set Disjointness on a Line は分散コンピューティングシナリオにおける Set Disjointness 問題の変種である。 条件のない$widetildeOmegabig(sqrt[3]n d2+sqrtn, big)$$$$d + 1$プロセッサを持つライン上の集合不整合のラウンドを証明する。
  論文  参考訳（メタデータ） (2020-02-26T21:17:53Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。