論文の概要: Hardness of Range Avoidance and Proof Complexity Generators from Demi-Bits

• arxiv url: http://arxiv.org/abs/2511.14061v1
• Date: Tue, 18 Nov 2025 02:40:39 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-11-19 16:23:52.883682
• Title: Hardness of Range Avoidance and Proof Complexity Generators from Demi-Bits
• Title（参考訳）: デミビットからのレンジ回避と証明複雑度発生器の硬さ
• Authors: Hanlin Ren, Yichuan Wang, Yan Zhong,
• Abstract要約: 非決定論的アルゴリズムでは、demi-bits ジェネレータの存在は$textAvoid$ が難しいことを示す。 我々はデミビット生成器を *pseudo-surjective* でほぼ最適パラメータを持つ複雑性生成器の証明に変換する。
• 参考スコア（独自算出の注目度）: 5.130304470169084
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Given a circuit $G: \{0, 1\}^n \to \{0, 1\}^m$ with $m > n$, the *range avoidance* problem ($\text{Avoid}$) asks to output a string $y\in \{0, 1\}^m$ that is not in the range of $G$. Besides its profound connection to circuit complexity and explicit construction problems, this problem is also related to the existence of *proof complexity generators* -- circuits $G: \{0, 1\}^n \to \{0, 1\}^m$ where $m > n$ but for every $y\in \{0, 1\}^m$, it is infeasible to prove the statement "$y\not\in\mathrm{Range}(G)$" in a given propositional proof system. This paper connects these two problems with the existence of *demi-bits generators*, a fundamental cryptographic primitive against nondeterministic adversaries introduced by Rudich (RANDOM '97). $\bullet$ We show that the existence of demi-bits generators implies $\text{Avoid}$ is hard for nondeterministic algorithms. This resolves an open problem raised by Chen and Li (STOC '24). Furthermore, assuming the demi-hardness of certain LPN-style generators or Goldreich' PRG, we prove the hardness of $\text{Avoid}$ even when the instances are constant-degree polynomials over $\mathbb{F}_2$. $\bullet$ We show that the dual weak pigeonhole principle is unprovable in Cook's theory $\mathsf{PV}_1$ under the existence of demi-bits generators secure against $\mathbf{AM}$, thereby separating Jerabek's theory $\mathsf{APC}_1$ from $\mathsf{PV}_1$. $\bullet$ We transform demi-bits generators to proof complexity generators that are *pseudo-surjective* with nearly optimal parameters. Our constructions build on the recent breakthroughs on the hardness of $\text{Avoid}$ by Ilango, Li, and Williams (STOC '23) and Chen and Li (STOC '24). We use *randomness extractors* to significantly simplify the construction and the proof.
• Abstract（参考訳）: 回路 $G: \{0, 1\}^n \to \{0, 1\}^m$ with $m > n$ が与えられたとき、*range avoidance* problem$\text{Avoid}$) は$G$の範囲にない文字列 $y\in \{0, 1\}^m$ を出力するように要求する。 回路複雑性と明示的な構成問題との深い関係に加えて、この問題は *proof complexity generators* -- circuits $G: \{0, 1\}^n \to \{0, 1\}^m$ where $m > n$ しかし、すべての$y\in \{0, 1\}^m$に対して、与えられた命題証明システムにおいて「$y\not\in\mathrm{Range}(G)$」という文を証明することは不可能である。 本稿では、これら2つの問題と、Rudich (RANDOM '97) が導入した非決定論的敵に対する基本的な暗号プリミティブである *demi-bits generators* の存在を結びつける。 さらに、あるLPN型ジェネレータやゴールドライヒのPRGのデミ硬度を仮定すると、例が$\mathbb{F}_2$上の定数次多項式であっても、$\text{Avoid}$の硬さを証明できる。 $\bullet$ 二重弱ハトホールの原理は、デミビット発生器が$\mathbf{AM}$に対して安全であることの下で、クック理論において証明不可能であることを示し、Jerabek の理論を $\mathsf{APC}_1$ から $\mathsf{PV}_1$ から分離する。 $\bullet$デミビットジェネレータを、ほぼ最適なパラメータを持つ *pseudo-surjective* である複雑性ジェネレータの証明に変換する。 Ilango, Li, and Williams (STOC '23) と Chen and Li (STOC '24) による$\text{Avoid}$ の難易度に関する最近の成果に基づいて構築した。 我々は*ランダム性抽出器*を用いて、構築と証明を著しく単純化する。

関連論文リスト

• Efficiently Batching Unambiguous Interactive Proofs [8.993111413196559]
  例えば、$Lotimes k$に属するステートメントのセット$k$-tuplesは、複雑さを伴うあいまいなインタラクティブな証明を持つ。 $ellcdotmathsfpolylog(k)$、$acdot ellcdotmathsfpolylog(k)$、ラウンドごとの通信である。
  論文  参考訳（メタデータ） (2025-10-21T21:04:10Z)
• Information-Computation Tradeoffs for Noiseless Linear Regression with Oblivious Contamination [65.37519531362157]
  このタスクに対する効率的な統計的クエリアルゴリズムは、VSTATの複雑さを少なくとも$tildeOmega(d1/2/alpha2)$で要求する。
  論文  参考訳（メタデータ） (2025-10-12T15:42:44Z)
• $\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)
• Approximating the operator norm of local Hamiltonians via few quantum states [53.16156504455106]
  複素ヒルベルト空間上で作用するエルミート作用素 $A$ を 2n$ とする。 A$ がパウリ拡大において小さな次数を持つとき、あるいは言い換えれば、$A$ は局所 $n$-量子ハミルトニアンである。 A$ が $d$-local, textiti.e., $deg(A)le d$ であるときは常に、次の離散化型不等式を持つことを示す。
  論文  参考訳（メタデータ） (2025-09-15T14:26:11Z)
• The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
  この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。 アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
  論文  参考訳（メタデータ） (2024-10-26T06:21:42Z)
• Monge-Kantorovich Fitting With Sobolev Budgets [6.748324975906262]
  我々は、$rho$が$mtext-d$集合の近くに集中しているとき、これをノイズのあるデータを持つ多様体学習問題と解釈できることを示した。 Monge-Kantorovich $p$-cost $mathbbW_pp(rho, nu)$を介して$rho$を近似する際の$nu$のパフォーマンスを定量化し、$mathrmsupp nu$を$f : mathbbRmでカバーできるようにすることで複雑さを制限します。
  論文  参考訳（メタデータ） (2024-09-25T01:30:16Z)
• 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)

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

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