論文の概要: Communication Complexity of Integer Matrix Singularity

• arxiv url: http://arxiv.org/abs/2610.33521v1
• Date: Sat, 24 Oct 2026 08:01:29 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-27 22:27:13.352564
• Title: Communication Complexity of Integer Matrix Singularity
• Title（参考訳）: 整数行列特異性の通信複雑性
• Abstract要約: 我々は、有界な量子下界$(minn3/2sqrtklog n,n2log(nk))$とランダム化された上界$O(n2mink,log(k+log n))$を証明する。 証明では整数証人と局所的な桁エンコーディングを組み合わせ,上行プロトコルは短いメッセージを使ってモジュールカーネルの関係を持ち上げる。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Alice and Bob hold complementary halves of the columns of an $n\times n$ matrix of $k$-bit integers and decide whether it is singular over $\mathbb Q$. Up to constant-factor dimension growth, this partitioned problem is equivalent to additive singularity, where Alice and Bob hold $n\times n$ matrices $A,B$ of $k$-bit integers and test the singularity of $A+B$ over $\mathbb Q$. We prove a bounded-error quantum lower bound $Ω(\min\{n^{3/2}\sqrt{k\log n},n^2\log(nk)\})$ and a randomized upper bound $O(n^2\min\{k,\log(k+\log n)\})$. The bounds match at $Θ(n^2\log(nk))$ for $k\ge n\log n$. The lower bound holds even under the promise of rank $n-1$ versus $n$. Its proof combines an integer witness with a local digit encoding, while the upper-bound protocol lifts modular kernel relations using short messages. Bitwise sharing changes how the communication complexity depends on the entry bit length $k$. If Alice and Bob instead hold $n\times n$ matrices $A,B$ of $k$-bit integers and test whether their entrywise bitwise XOR $A\oplus B$ is singular over $\mathbb Q$, we prove a quantum lower bound $Ω(n^2k)$, matching the trivial upper bound. This lower bound holds even under the promise of rank $n-1$ versus $n$. Our proof uses a dense weighted equation and a signed Fourier witness whose exceptional dyadic frequencies can be removed at small variation cost.
• Abstract（参考訳）: Alice と Bob は、$n\times n$ matrix of $k$-bit integers の列の補的ハーフを持ち、$\mathbb Q$ よりも特異であるかどうかを決定する。 ここで、アリスとボブは$n\times n$ matrices $A,B$ of $k$-bit integers を持ち、$A+B$ over $\mathbb Q$ の特異点をテストする。 我々は、有界な量子下界$Ω(\min\{n^{3/2}\sqrt{k\log n},n^2\log(nk)\})$とランダム化された上界$O(n^2\min\{k,\log(k+\log n)\})$を証明する。 境界は、$k\ge n\log n$ に対して$(n^2\log(nk))$ と一致する。 下限は$n-1$と$n$の約束でも成り立つ。 その証明は整数証人と局所桁の符号化を組み合わせ、上行プロトコルは短いメッセージを使ってモジュラーカーネルの関係を持ち上げる。 ビットワイズ共有は、通信の複雑さがエントリビット長$k$に依存する方法を変える。 Alice と Bob が代わりに$n\times n$ matrices $A,B$ of $k$-bit integers を持ち、そのエントリワイズビットワイズ XOR $A\oplus B$ が $\mathbb Q$ 上特異であるかどうかをテストすると、自明な上界に一致する量子下界 $Ω(n^2k)$ が証明される。 この下限は、$n-1$対$n$の約束でも成り立つ。 我々の証明は密度重み付き方程式と符号付きフーリエ証人を用いており、例外的なダイアディック周波数を小さな変動コストで除去することができる。

関連論文リスト

• Characterizing Quantum Advantage for Generalizations of the Boolean Hidden Matching Problem [5.457853441330696]
  本稿では,$f$-Boolean Hidden 分割問題の一方的な通信複雑性について検討する。 古典的および量子的通信境界を$f$-Boolean Hidden Partitionに対して確立する。
  論文  参考訳（メタデータ） (2026-10-05T17:48:13Z)
• Computational Bounds for $f$-Routing [1.2604738912025477]
  我々は、一様攻撃者に対する無条件リソースの低い境界を証明した。 入力長 $n$ と十分小さい定数 $>0$ に対して、$q$ qubits を用いた一様生成戦略は、以下の計算境界を$f$ で表している。 これらの境界は、内積関数 $f=mathrmIP$ に対して、Bluhm, Christandl, Speelman (2022) の$qlelog n$ を超える。
  論文  参考訳（メタデータ） (2026-09-30T17:46:42Z)
• Sharp Minimax Regret for Infinite-Memory Logistic Prediction [55.29259818039367]
  Lag $j$はスケール$r_j$の予測に影響を与え、$n_T,j=T-j+1$の予測ラウンドに入る。 すべての要約可能なエンベロープに対して、局所化された混合は$cR_T(r)leq C_T(r)$を証明する。 指数関数やエンベロープの場合、有限サンプル条件の下では、トープリッツ・デサインの逆は$cR_T(r)geq c_T(r)$である。
  論文  参考訳（メタデータ） (2026-08-27T01:31:46Z)
• Quantum Search With Generalized Wildcards [0.4310167974376404]
  我々は、コスト$O(sqrtn log n)$の量子アルゴリズムと、ほぼ一致する$Omega(sqrtn)$の低い境界を示す。 以下に示すように、$calQ$が有界サイズセット、連続ブロック、プレフィックス、フルセットのみである場合に、ほぼタイトなバウンダリを表示する。
  論文  参考訳（メタデータ） (2025-11-06T18:55:05Z)
• $\mathsf{P} \neq \mathsf{NP}$: A Non-Relativizing Proof via Quantale Weakness and Geometric Complexity [0.0]
  We work in the weak Quantale $w_Q=K_mathrmpoly(cdotmidcdot)$. ランダムな3ドルCNFをマスキングした効率よくサンプリング可能なアンサンブル$D_m$に対して、スイッチング・バイ・ウェイクネスの正規形式を証明する。
  論文  参考訳（メタデータ） (2025-10-09T21:01:17Z)
• The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
  この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。 アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
  論文  参考訳（メタデータ） (2024-10-26T06:21:42Z)
• Monogamy of entanglement between cones [43.57338639836868]
  モノガミーは量子論の特徴であるだけでなく、凸錐の一般対の極小テンソル積を特徴づけることを示した。 我々の証明は、アフィン同値まで単純化された生成物の新たな特徴を生かしている。
  論文  参考訳（メタデータ） (2022-06-23T16:23:59Z)
• Low-degree learning and the metric entropy of polynomials [44.99833362998488]
  少なくとも$Omega(sqrtvarepsilon)2dlog n leq log mathsfM(mathscrF_n,d,|cdot|_L,varepsilon)は2辺の推定値$c(1-varepsilon)2dlogを満たす。
  論文  参考訳（メタデータ） (2022-03-17T23:52:08Z)
• An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
  すべての決定木に対して、与えられた順序 $ellsqrtbinomdell (1+log n)ell-1,$ sum to at least $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, $c>0$ is a absolute constant。
  論文  参考訳（メタデータ） (2020-08-24T06:50:57Z)
• Tight Quantum Lower Bound for Approximate Counting with Quantum States [49.6558487240078]
  Aaronson, Kothari, Kretschmer, Thaler (2020) が考える数え上げ問題の次の変種に対する厳密な下界を証明する。 このタスクは、入力セット$xsubseteq [n]$が$k$か$k'=(1+varepsilon)k$であるかどうかを識別する。
  論文  参考訳（メタデータ） (2020-02-17T10:53:50Z)

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

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