論文の概要: A Note on Binary Quadratic Systems and their relation to complexity theory

• arxiv url: http://arxiv.org/abs/2609.07769v1
• Date: Mon, 07 Sep 2026 17:19:05 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-09-11 21:07:32.575617
• Title: A Note on Binary Quadratic Systems and their relation to complexity theory
• Title（参考訳）: 二項二次系とその複雑性理論との関係についての一考察
• Abstract要約: Q_d$の評価マトロイドの基底集合として$(FF_2)n$を証明します。 また、ホイットニー型符号反転の帰納法を用いて、マトロイドポートの要素から$_1/2n$以下に$_1/2n$をプッシュできる条件のみを示す。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Deciding whether a system of multivariate quadratic equations over $\mathbb F_2$ has a solution is a classical NP-complete problem, and remains so for square systems, with as many equations as variables. The hardness of this problem is one of the cornerstones of nowadays post-quantum cryptography. Let $\MQ_0(n)$ and $\MQ_1(n)$ denote the sets of square quadratic systems in $n$ variables having respectively no solutions and exactly one solution. $\cup_{n\geq 2} \MQ_0(n)$ is a coNP-complete language, while $\cup_{n\geq 2} \MQ_1(n)$ lies in DP. It is known that $\lim_{n\to \infty} |\MQ_1(n)|/|\MQ_0(n)|=1$. Here we prove the explicit finite-$n$ bounds \[ |\MQ_0(n)|<|\MQ_1(n)| \le \left(1+\frac{1}{2^n-1}\right)|\MQ_0(n)|, \] More generally, let $Q_d$ be the space of polynomial functions $(\FF_2)^n\to\mathbb F_2$ of degree at most $d$, and let $α_k$ count square systems in $(Q_d)^n$ having exactly $k$ solutions. Then \[ α_0<α_1 \le \left(1+\frac{1}{2^n-1}\right)α_0\,, \qquad 2\le d\le n \,. \] The proof combines matroid and coding-theoretic methods. We interpret $(\FF_2)^n$ as the ground set of the evaluation matroid of $Q_d$, express $α_0$ and $α_1$ through characteristic polynomials, and use a Whitney-type sign-reversing involution to show that the only terms that can push $α_1-α_0$ below $α_1/2^n$ come from the elements of a matroid port. These are identified with minimal-support words of the Reed--Muller code $\RM(n-d-1,n)=\RM(d,n)^\perp$; the required estimate then follows from the MacWilliams identity, the minimum-distance bound $2^{d+1}$, and the even-weight structure of the code.
• Abstract（参考訳）: $\mathbb F_2$ 上の多変数二次方程式の系が解を持つかどうかを決定することは古典的なNP完全問題であり、変数として多くの方程式を持つ正方系の問題である。 この問題の難しさは、今日の量子後暗号の基盤の1つである。 $\MQ_0(n)$ と $\MQ_1(n)$ は、それぞれに解とちょうど1つの解を持たない$n$変数の平方二次系の集合を表す。 $\cup_{n\geq 2} \MQ_0(n)$はcoNP完全言語であり、$\cup_{n\geq 2} \MQ_1(n)$はDPに含まれる。 $\lim_{n\to \infty} |\MQ_1(n)|/|\MQ_0(n)|=1$であることが知られている。 ここでは、明示的な有限-$n$束 \[|\MQ_0(n)|<|\MQ_1(n)| \le \left(1+\frac{1}{2^n-1}\right)|\MQ_0(n)|, \] を証明する。 このとき、[α_0<α_1 \le \left(1+\frac{1}{2^n-1}\right)α_0\,, \qquad 2\le d\le n \, この証明は、マトロイドとコーディング理論の手法を組み合わせている。 Q_d$ の評価マトロイドの基底集合として $(\FF_2)^n$ を解釈し、特徴多項式を通して $α_0$ と $α_1$ を表現し、Whitney 型符号逆変換を用いて、$α_1-α_0$ を $α_1/2^n$ 以下に押すことができる唯一の項が、マトロイドポートの要素から来ることを示す。 これらはReed-Muller符号の最小サポート語 $\RM(n-d-1,n)=\RM(d,n)^\perp$ と同一視される。

関連論文リスト

• Faster quantum linear system solver beyond the condition number [50.84794327094274]
  線形系の正規化解 $|xrangle$ を生成する2つの量子アルゴリズムを、条件数$=lVert A-1rVert$ に依存しない複雑性を持つ精度 $Ax=| b rangle$ に提示する。 フィルタベースのソルバは非常にシンプルで、実行時プレファクタが適しています。
  論文  参考訳（メタデータ） (2026-07-08T17:49:40Z)
• Rényi exponent landscape of multipartite entanglement in free-fermion systems [51.56484100374058]
  我々は、Rényi tripartite information $I_3() が小フェルミ運動量での質的に $exclusion-dependent scaling を示すことを示した。 I_m(n)/I_m(1) sim zm-1 to 0$ for all integer $n geq 2$, so the leading von Neumann signal can builded from integer Rényi data。
  論文  参考訳（メタデータ） (2026-03-09T22:27:00Z)
• Quantum Search With Generalized Wildcards [0.4310167974376404]
  我々は、コスト$O(sqrtn log n)$の量子アルゴリズムと、ほぼ一致する$Omega(sqrtn)$の低い境界を示す。 以下に示すように、$calQ$が有界サイズセット、連続ブロック、プレフィックス、フルセットのみである場合に、ほぼタイトなバウンダリを表示する。
  論文  参考訳（メタデータ） (2025-11-06T18:55:05Z)
• Information-Computation Tradeoffs for Noiseless Linear Regression with Oblivious Contamination [65.37519531362157]
  このタスクに対する効率的な統計的クエリアルゴリズムは、VSTATの複雑さを少なくとも$tildeOmega(d1/2/alpha2)$で要求する。
  論文  参考訳（メタデータ） (2025-10-12T15:42:44Z)
• $\mathsf{P} \ eq \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)
• A polynomial quantum computing algorithm for solving the dualization problem [75.38606213726906]
  2つの単調素関数 $f:0,1n to 0,1$ と $g:0,1n to 0,1$ が与えられたとき、双対化問題は$g$が$f$の双対かどうかを決定することである。 本稿では,双対化問題の決定版を時間内に解く量子コンピューティングアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-08-28T18:12:54Z)
• The Approximate Degree of DNF and CNF Formulas [95.94432031144716]
  すべての$delta>0に対して、$はCNFと近似次数$Omega(n1-delta)の式を構築し、基本的には$nの自明な上限に一致する。 すべての$delta>0$に対して、これらのモデルは$Omega(n1-delta)$、$Omega(n/4kk2)1-delta$、$Omega(n/4kk2)1-delta$が必要です。
  論文  参考訳（メタデータ） (2022-09-04T10:01:39Z)
• 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)
• Threshold Phenomena in Learning Halfspaces with Massart Noise [56.01192577666607]
  ガウス境界の下でのマスアートノイズ付きmathbbRd$におけるPAC学習ハーフスペースの問題について検討する。 この結果は,Massartモデルにおける学習ハーフスペースの複雑さを定性的に特徴づけるものである。
  論文  参考訳（メタデータ） (2021-08-19T16:16:48Z)
• Learning sums of powers of low-degree polynomials in the non-degenerate case [2.6109033135086777]
  我々は、ある非退化条件が成立すれば、同じモデルに対する下界から算術回路モデルの学習アルゴリズムを与える。 本アルゴリズムは,同じモデルに対する下界から算術回路モデルの学習アルゴリズムを得るためのスキームに基づいている。
  論文  参考訳（メタデータ） (2020-04-15T06:18:41Z)

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

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