论文标题
$ \ text {ac}^0 $公式的关键性
Criticality of $\text{AC}^0$ formulae
论文作者
论文摘要
罗斯曼[in $ \ textit {proc。 $ 34 $ TH Comput。复杂性conf。} $，2019年]介绍了$ \ textit {criticality} $的概念。布尔函数的关键$ f：\ {0,1 \}^n \ to \ {0,1 \} $是最小$ $ $λ\ geq 1 $，以至于所有正整数$ t $，\ [\ pr_ pr_ [\ pr_ {ρ\ sim {ρ\ sim） \ Mathcal {r} _p} \ left [\ text {dt} _ {\ text {depth}}}}}（f |_ρ）\ geq t \ right] \ leq（pλ）^t。 \]Hästad的著名切换引理表明，任何$ k $ -dnf的关键最多都是$ o（k）$。随后对$ \ text {ac}^0 $ cirt抗平价的相关范围的改进表明，任何$ \ text {ac}^0 $ - $ - $ - $ - $ \ textit {courtivit {courtile} $ size $ s $ s $和depth $ d+d+d+d+d+1 $最多是$ o（\ log s） $ \ text {ac}^0 $ - $ \ textit {公式} $ $ s $和depth $ d+1 $的$最多是$ o \ left（\ frac1d \ cdot \ cdot \ log s \ s \ right）^d $。我们通过表明$ \ textit {any} $ $ \ text {ac}^0 $ -formula（不一定是规则的）和depth $ s $和depth $ d+1 $的关键性最多是$ o \ weft（\ frac1d \ cdot {\ cdot s}} d $，以下是命令， 该结果还意味着罗斯曼的最佳下限在任何深度 - $ d $ \ text {ac}^0 $ -formula Computing Parity [$ \ textit {comput {comput。复杂性，27（2）：209--223，2018。} $]。我们的结果意味着与奇偶校验的紧密相关范围，紧密的傅立叶浓度结果，并改进了$ \ text {ac}^0 $ -formulae的$ \＃$ SAT算法。
Rossman [In $\textit{Proc. $34$th Comput. Complexity Conf.}$, 2019] introduced the notion of $\textit{criticality}$. The criticality of a Boolean function $f : \{0,1\}^n \to \{0,1\}$ is the minimum $λ\geq 1$ such that for all positive integers $t$, \[ \Pr_{ρ\sim \mathcal{R}_p}\left[\text{DT}_{\text{depth}}(f|_ρ) \geq t\right] \leq (pλ)^t. \] Hästad's celebrated switching lemma shows that the criticality of any $k$-DNF is at most $O(k)$. Subsequent improvements to correlation bounds of $\text{AC}^0$-circuits against parity showed that the criticality of any $\text{AC}^0$-$\textit{circuit}$ of size $S$ and depth $d+1$ is at most $O(\log S)^d$ and any $\textit{regular}$ $\text{AC}^0$-$\textit{formula}$ of size $S$ and depth $d+1$ is at most $O\left(\frac1d \cdot \log S\right)^d$. We strengthen these results by showing that the criticality of $\textit{any}$ $\text{AC}^0$-formula (not necessarily regular) of size $S$ and depth $d+1$ is at most $O\left(\frac1d\cdot {\log S}\right)^d$, resolving a conjecture due to Rossman. This result also implies Rossman's optimal lower bound on the size of any depth-$d$ $\text{AC}^0$-formula computing parity [$\textit{Comput. Complexity, 27(2):209--223, 2018.}$]. Our result implies tight correlation bounds against parity, tight Fourier concentration results and improved $\#$SAT algorithm for $\text{AC}^0$-formulae.
