← 研踪 PaperTrailarXiv:2610.40397 · v1
Random ($\log{n}$)-CNF Formulas Are Hard for Depth-$2$ Frege with Modular Gates
首次提交 2026-10-30 00:33
版本更新 2026-10-30 00:33
雷达观测 2026-10-30 13:28
摘要
We prove that, with high probability, refuting a random $k$-CNF formula on $n$ variables with ${M = n2^{k}}$ clauses for $ω_n(1) \leq k \leq O(\log{n})$ requires polynomial calculus degree at least ${n/2-O(n/\sqrt{k})}$ over every field. Through Pang's recent tradeoff between $\mathsf{AC}^0[p]$-Frege size and polynomial calculus degree [Pang 2026, arXiv:2610.00837v2], this implies a size lower bound of $\exp(Ω_p(\sqrt{k} \log{n}))$ for depth-$2$ $\mathsf{AC}^0[p]$-Frege. In this range of $k$, the bound is superpolynomial in $M$ while $M \leq \mathrm{poly}(n)$. We also prove a nearly matching degree upper bound of $n/2-n\ln(k)/{2k} +O(n/k)$, which shows that other formula families are needed to obtain lower bounds for full $\mathsf{AC}^0[p]$-Frege through Pang's tradeoff.
观测到的版本
相邻记录可能跳过中间版本；首次发现 v2 及以上也会标为版本更新。
v1 · 2026-10-30 00:33 · 最新观测版本
Random ($\log{n}$)-CNF Formulas Are Hard for Depth-$2$ Frege with Modular Gates
We prove that, with high probability, refuting a random $k$-CNF formula on $n$ variables with ${M = n2^{k}}$ clauses for $ω_n(1) \leq k \leq O(\log{n})$ requires polynomial calculus degree at least ${n/2-O(n/\sqrt{k})}$ over every field. Through Pang's recent tradeoff between $\mathsf{AC}^0[p]$-Frege size and polynomial calculus degree [Pang 2026, arXiv:2610.00837v2], this implies a size lower bound of $\exp(Ω_p(\sqrt{k} \log{n}))$ for depth-$2$ $\mathsf{AC}^0[p]$-Frege. In this range of $k$, the bound is superpolynomial in $M$ while $M \leq \mathrm{poly}(n)$. We also prove a nearly matching degree upper bound of $n/2-n\ln(k)/{2k} +O(n/k)$, which shows that other formula families are needed to obtain lower bounds for full $\mathsf{AC}^0[p]$-Frege through Pang's tradeoff.
查看此版本解读 →查看此版本原文 ↗