We prove both a conditional and a fully analytic unconditional lower bound against $\mathsf{AC}^0$ circuits for a natural distribution over random satisfiable $3$–CNF formulas with $\Theta(n)$ clauses at constant density.
For any constant depth $d$ and polynomial size $n^k$, such circuits fail to decide satisfiability with probability at least $2/3$ conditioned on a natural non-triviality event~$\mathcal{E}$, which excludes degenerate cases where the restricted formula becomes constant with high probability.
In our model $\Prb[\mathcal{E}]\ge\gamma>0$, so the conditional bound implies an unconditional bound scaled by~$\gamma$.
In addition, we prove—without empirical assumptions—a fixed-window unconditional lower bound, by analytically bounding the probabilities of trivialization and imbalance, and combining these bounds with the Håstad switching-lemma pipeline.
This yields a correlation gap strictly below $1/2$ for all small-depth decision trees at some $p^\star$ in the window.
Our formulation makes all constants explicit, includes reproducibility data for empirical scans, and provides a clear benchmark within the $\mathsf{AC}^0$ lower-bound program.
Added a fully analytic unconditional in-window lower bound to complement the conditional main theorem.
This includes formal proofs of uniform non-triviality, no-mass-kill bounds, constant balance probability, and an unconditional correlation gap theorem.
Updated Section titles and remarks to highlight the unconditional result, and kept all constants explicit.
Extended the reproducibility checklist and Part 4 to document coverage and drift-stability metrics in the chosen parameter window.
We prove that for a natural distribution over random satisfiable 3--CNF formulas with $\Theta(n)$ clauses, every $\mathsf{AC}^0$ circuit family of constant depth $d$ and polynomial size $n^k$ fails to decide satisfiability with probability at least $2/3$ under the standard random restriction method with parameter $p = n^{-1/(2d)}$. The proof follows the classical Håstad switching-lemma framework with explicit parameterization: we choose optimal restriction parameters, argue a collapse to small decision trees, and derive a contradiction with correctness on the induced sub-instances. This explicit bound, stated for satisfiable instances at constant clause density, provides a clear benchmark within the $\mathsf{AC}^0$ lower-bound program.
Extended with an unconditional in-window bound formulation and added reproducibility links.
We prove a conditional lower bound against $\mathsf{AC}^0$ circuits for a natural distribution over random satisfiable 3--CNF formulas with $\Theta(n)$ clauses.
For any constant depth $d$ and polynomial size $n^k$, such circuits fail to decide satisfiability with probability at least $2/3$ conditioned on a non-triviality event $\mathcal{E}$, which excludes degenerate cases where the restricted formula becomes constant with high probability.
In the satisfiable constant-density model, $\Pr[\mathcal{E}] \ge \gamma > 0$, so the conditional bound yields an unconditional bound scaled by $\gamma$.
No claim is made about hardness outside $\mathcal{E}$.
The proof uses the H{\aa}stad switching lemma with explicit constants, and we include synthetic-data heatmaps for illustration only.
Clarified that Theorem~3.1 is conditional on the non-triviality event $\mathcal{E}$, and that no hardness claim is made outside $\mathcal{E}$.
Added explicit definition of $\gamma$ and its role.
Rephrased empirical figure captions to emphasize their purely illustrative nature.
Minor wording changes for clarity; no change to main proof or bounds.
We prove that for a natural distribution over random satisfiable 3–CNF formulas with \Theta(n) clauses, every \mathrm{AC}^0 circuit family of constant depth d and polynomial size n^k fails to decide satisfiability with probability at least 2/3, conditioned on a natural non-triviality event \mathcal{E} that excludes degenerate constant functions, under the standard random restriction method with parameter p=n^{-1/(2d)}. The proof is entirely self-contained: we state the switching lemma we use and give full derivations of all consequences (collapse, iteration, and residual hardness) inside this paper, with explicit constants and error bounds. We also introduce a balanced restriction refinement yielding a correlation gap strictly below 1/2 for bounded-depth decision trees.
Added explicit conditioning on a non-triviality event \mathcal{E} in the main theorem, abstract, and proof, to exclude degenerate constant functions. Added a remark explaining \mathcal{E} and clarified that \Pr[\mathcal{E}] is bounded below by a constant. No other changes to the proof or bounds.
We prove that for a natural distribution over random satisfiable 3–CNF formulas with \Theta(n) clauses, every \mathrm{AC}^0 circuit family of constant depth d and polynomial size n^k fails to decide satisfiability with probability at least 2/3 conditioned on a non-triviality event \mathcal{E} under the standard random restriction method with parameter p = n^{-1/(2d)}. The event \mathcal{E} excludes degenerate cases where the restricted formula becomes constant with high probability, ensuring that residual hardness applies to genuinely non-trivial instances. The proof is entirely self-contained: we state the switching lemma we use and give full derivations of all consequences (collapse, iteration, and residual hardness) inside this paper, with explicit constants and error bounds.
Added explicit non-triviality event \mathcal{E} to exclude degenerate constant-function cases pointed out by Oded Goldreich. All hardness statements are now conditioned on \mathcal{E}, with a proof that \Pr[\mathcal{E}] \ge \gamma > 0 for some constant \gamma independent of n. Updated Theorem 3.1, Lemma 3.3, and Remark 4.1 accordingly. Abstract updated to mention conditioning on \mathcal{E}.
We prove that for a natural distribution over random satisfiable 3–CNF formulas with $\Theta(n)$ clauses, every $\AC^0$ circuit family of constant depth $d$ and polynomial size $n^k$ fails to decide satisfiability with probability at least $2/3$ under the standard random restriction method with parameter $p=n^{-1/(2d)}$. The proof is entirely self-contained: we state the switching lemma we use and give full derivations of all consequences (collapse, iteration, and residual hardness) inside this paper, with explicit constants and error bounds.
In addition, Lemma~\ref{lem:gap} introduces a balance-filtered restriction distribution yielding a fixed correlation gap below $1/2$ for bounded-depth decision trees, a strengthening not explicitly stated in prior work.
Added Remark clarifying choice of p and balance filter;
introduced Lemma~\ref{lem:gap} giving a correlation gap below 1/2 for bounded-depth decision trees;
updated Relation to Prior Work and Appendix with full parameter details.
We prove that for a natural distribution over random satisfiable 3--CNF formulas with $\Theta(n)$ clauses, every $\mathsf{AC}^0$ circuit family of constant depth $d$ and polynomial size $n^k$ fails to decide satisfiability with probability at least $2/3$ under the standard random restriction method with parameter $p = n^{-1/(2d)}$. The proof follows the classical Håstad switching-lemma framework with explicit parameterization: we choose optimal restriction parameters, argue a collapse to small decision trees, and derive a contradiction with correctness on the induced sub-instances. This explicit bound, stated for satisfiable instances at constant clause density, provides a clear benchmark within the $\mathsf{AC}^0$ lower-bound program.
Adopted the standard Håstad convention for $p$ (leave probability), updated Section 2, Lemma 3.4, and Appendix A accordingly; no change to main theorem or bounds.
Keywords:
AC0, lower bounds, random restrictions, switching lemma, 3-CNF, satisfiability
We prove that for a natural distribution over random satisfiable 3--CNF formulas with $\Theta(n)$ clauses, every $\mathsf{AC}^0$ circuit family of constant depth $d$ and polynomial size $n^k$ fails to decide satisfiability with probability at least $2/3$ under the standard random restriction method with parameter $p = n^{-1/(2d)}$. The proof follows the classical Håstad switching-lemma framework with explicit parameterization: we choose optimal restriction parameters, argue a collapse to small decision trees, and derive a contradiction with correctness on the induced sub-instances. This explicit bound, stated for satisfiable instances at constant clause density, provides a clear benchmark within the $\mathsf{AC}^0$ lower-bound program.
This is just to clarify that I did not look at the paper carefully.
In particular, I'm not sure what Thm 3.1 claims.
When there is no conditioning, it seems that, wvhp, phi restricted to rho is the all zero function.
On the other hand, if the conditional distribution of the resulting formula is not "dull" (say, has min-entropy at least 1), then no circuit (regardless of it size) can compute a formula drawn from this distribution. Furthermore, if for some rho, the conditional distribution of the resulting formula is non-dull, then the same holds even when the circuit may depend on rho.
Adopted the standard Håstad convention for p as the leave probability
(unset with probability p, fixed to 0 or 1 with probability (1-p)/2 each).
Updated Section 2, Lemma 3.4, and Appendix A accordingly.
No changes to the main theorem or bounds.
This report (TR25-124) has been withdrawn by the author after recognizing a flaw in the main argument.
No resubmission to ECCC is intended.
A revised version addressing these issues may appear elsewhere.
