Hardness of Range Avoidance and Proof Complexity Generators from Demi-Bits

• URL: http://arxiv.org/abs/2511.14061v1
• Date: Tue, 18 Nov 2025 02:40:39 GMT
• Title: Hardness of Range Avoidance and Proof Complexity Generators from Demi-Bits
• Abstract summary: We show that the existence of demi-bits generators implies $textAvoid$ is hard for nondeterministic algorithms.<n>We transform demi-bits generators to proof complexity generators that are *pseudo-surjective* with nearly optimal parameters.
• Score: 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.

Related papers

• A Note on Binary Quadratic Systems and their relation to complexity theory [0.0]
  We prove $(FF_2)n$ as the ground set of the evaluation matroid of $Q_d$.<n>We also use a Whitney-type sign-reversing involution to show that only terms that can push $_1/2n$ below $_1/2n$ come from the elements of a matroid port.
  arXiv  Detail & Related papers  (2026-09-07T17:19:05Z)
• The Condition-Number Barrier in Sparse Least Squares [77.64108812086542]
  In [AS21], Axiotis and Sviridenko conjectured that the linear dependence on the restricted condition number in convex optimization cannot be improved by a sparse-time algorithm.<n>We establish their conjectured lower bound for least-squares objectives, conditional on the randomized exact-volume Small-Set Expansion Hypothesis.
  arXiv  Detail & Related papers  (2026-08-03T17:57:01Z)
• Regularization of Divergent Power Sums via Fractional Extension of Differential Generators [0.0]
  We consider the regularization of the divergent sum $sum_n=1inftynm$ for every non-negative integer $m$.<n>The extension of the sum for non-integer $$ is obtained under the consistency condition that the regularized sum for integer $m$ emerges continuously from the sum for non-integer $$.
  arXiv  Detail & Related papers  (2026-04-26T05:42:13Z)
• Efficiently Batching Unambiguous Interactive Proofs [8.993111413196559]
  We show that if a language $L$ admits a publiccoin interactive proof (UIP) with round $ell$, where $a$ bits are communicated per round, then the batch language $Lotimes k$, i.e. the set of $k$-tuples of statements all belonging to $Lotimes k$, has unambiguous interactive proof with complexity $ellcdotmathsfpolylog(k)$, per-round communication of $acdot ellcdotmathsfpolylog(k
  arXiv  Detail & Related papers  (2025-10-21T21:04:10Z)
• Information-Computation Tradeoffs for Noiseless Linear Regression with Oblivious Contamination [65.37519531362157]
  We show that any efficient Statistical Query algorithm for this task requires VSTAT complexity at least $tildeOmega(d1/2/alpha2)$.
  arXiv  Detail & Related papers  (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 weakness quantale $w_Q=K_mathrmpoly(cdotmidcdot)$.<n>For an efficiently samplable ensemble $D_m$ made by masking random $3$-CNFs, we prove a Switching-by-Weakness normal form.
  arXiv  Detail & Related papers  (2025-10-09T21:01:17Z)
• Approximating the operator norm of local Hamiltonians via few quantum states [53.16156504455106]
  Consider a Hermitian operator $A$ acting on a complex Hilbert space of $2n$.<n>We show that when $A$ has small degree in the Pauli expansion, or in other words, $A$ is a local $n$-qubit Hamiltonian.<n>We show that whenever $A$ is $d$-local, textiti.e., $deg(A)le d$, we have the following discretization-type inequality.
  arXiv  Detail & Related papers  (2025-09-15T14:26:11Z)
• The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
  We show that this problem has randomized communication complexity $Omega(frac1kcdot n2log|mathbbF|)$. As an application, we obtain an $Omega(frac1kcdot n2log|mathbbF|)$ space lower bound for any streaming algorithm with $k$ passes.
  arXiv  Detail & Related papers  (2024-10-26T06:21:42Z)
• Monge-Kantorovich Fitting With Sobolev Budgets [6.748324975906262]
  We show that when $rho$ is concentrated near an $mtext-d$ set we may interpret this as a manifold learning problem with noisy data.<n>We quantify $nu$'s performance in approximating $rho$ via the Monge-Kantorovich $p$-cost $mathbbW_pp(rho, nu)$, and constrain the complexity by requiring $mathrmsupp nu$ to be coverable by an $f : mathbbRm
  arXiv  Detail & Related papers  (2024-09-25T01:30:16Z)
• A Unified Framework for Uniform Signal Recovery in Nonlinear Generative Compressed Sensing [68.80803866919123]
  Under nonlinear measurements, most prior results are non-uniform, i.e., they hold with high probability for a fixed $mathbfx*$ rather than for all $mathbfx*$ simultaneously. Our framework accommodates GCS with 1-bit/uniformly quantized observations and single index models as canonical examples. We also develop a concentration inequality that produces tighter bounds for product processes whose index sets have low metric entropy.
  arXiv  Detail & Related papers  (2023-09-25T17:54:19Z)
• Randomised Composition and Small-Bias Minimax [0.9252523881586053]
  We prove two results about query complexity $mathrmR(f)$. First, we introduce a "linearised" complexity measure $mathrmLR$ and show that it satisfies an inner-conflict composition theorem: $mathrmR(f) geq Omega(mathrmR(f) mathrmLR(g))$ for all partial $f$ and $g$, and moreover, $mathrmLR$ is the largest possible measure with this property.
  arXiv  Detail & Related papers  (2022-08-26T23:32:19Z)
• Learning a Single Neuron with Adversarial Label Noise via Gradient Descent [50.659479930171585]
  We study a function of the form $mathbfxmapstosigma(mathbfwcdotmathbfx)$ for monotone activations. The goal of the learner is to output a hypothesis vector $mathbfw$ that $F(mathbbw)=C, epsilon$ with high probability.
  arXiv  Detail & Related papers  (2022-06-17T17:55:43Z)
• Low-degree learning and the metric entropy of polynomials [44.99833362998488]
  We prove that any (deterministic or randomized) algorithm which learns $mathscrF_nd$ with $L$-accuracy $varepsilon$ requires at least $Omega(sqrtvarepsilon)2dlog n leq log mathsfM(mathscrF_n,d,|cdot|_L,varepsilon) satisfies the two-sided estimate $$c (1-varepsilon)2dlog
  arXiv  Detail & Related papers  (2022-03-17T23:52:08Z)
• Threshold Phenomena in Learning Halfspaces with Massart Noise [56.01192577666607]
  We study the problem of PAC learning halfspaces on $mathbbRd$ with Massart noise under Gaussian marginals. Our results qualitatively characterize the complexity of learning halfspaces in the Massart model.
  arXiv  Detail & Related papers  (2021-08-19T16:16:48Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.