论文标题
低通信叶门的De Morgan公式的算法和下限
Algorithms and Lower Bounds for de Morgan Formulas of Low-Communication Leaf Gates
论文作者
论文摘要
类$公式[s] \ Circ \ Mathcal {G} $由Boolean函数组成，可按大小-s $ s $ de Morgan公式计算，其叶子是$ \ Mathcal {G g} $的任何布尔函数。我们给出了$公式的算法和（SAT，Learning和PRG）算法[N^{1.99}] \ Circ \ Mathcal {G} $，用于$ \ Mathcal {G} $的函数的$ \ Mathcal {G} $，具有低通信复杂性。令$ r^{（k）}（\ Mathcal {g}）$为$ \ Mathcal {g} $的最大$ k $ - 部分NOF随机通信复杂性。我们显示： （1）在超过$ 1/2+\ varepsilon $上，$ circ \ circ \ mathcal {g} $无法以$ 1/2+\ varepsilon $输入的输入分数计算$ circula [s] \ Mathcal {g} $计算广义内部产品函数$ gip^k_n $。 \左（\ frac {n^2} {\ left（k \ cdot 4^k \ cdot {r}^{（k）}（\ Mathcal {g}）\ cdot \ cdot \ log（n/\ varepsilon）推论，我们获得了$ gip^k_n $的平均下限，$ gip^k_n $ to $公式[n^{1.99}] \ circ ptf^{k-1} $。 （2）有一个种子长度$ n/2 + o \左（\ sqrt {s} \ cdot r^{（2）}（\ Mathcal {g}）\ cdot \ cdot \ log（s/\ varepsilon）\ cdot \ cdot \ logepsilon）$ vareps $ \ c $ \ c $ \ \ Circ \ Mathcal {G} $。对于$公式[s] \ circ ltf $，我们得到更好的种子长度$ o \ left（n^{1/2} \ cdot s^{1/4} \ cdot \ cdot \ log（n）\ cdot \ cdot \ log（n/\ varepsilon）\ right）$。这给出了第一个非平凡的PRG（带有种子长度$ O（n）$），用于$ n $半空间的交集，其中$ \ varepsilon \ lepsilon \ leq 1/n $。 （3）有一个随机的$ 2^{n-t} $ - 时间$ \＃$ sat algorithm for $ formula [s] \ Circ \ Mathcal {g} $，其中$$ t =ω\ left（\ frac {n} {n} r^{（2）}（\ Mathcal {g}）} \ right）^{1/2}。$$，这意味着$公式[n^{1.99}] \ circ circ ltf $ for $公式[n^{1.99}]的非平凡#Sat算法。 （4）最小电路大小问题不在$公式[n^{1.99}] \ Circ Xor $中。在算法方面，我们表明$公式[n^{1.99}] \ circ xor $可以在时间$ 2^{o（n/\ log n）} $中进行PAC学习。
The class $FORMULA[s] \circ \mathcal{G}$ consists of Boolean functions computable by size-$s$ de Morgan formulas whose leaves are any Boolean functions from a class $\mathcal{G}$. We give lower bounds and (SAT, Learning, and PRG) algorithms for $FORMULA[n^{1.99}]\circ \mathcal{G}$, for classes $\mathcal{G}$ of functions with low communication complexity. Let $R^{(k)}(\mathcal{G})$ be the maximum $k$-party NOF randomized communication complexity of $\mathcal{G}$. We show: (1) The Generalized Inner Product function $GIP^k_n$ cannot be computed in $FORMULA[s]\circ \mathcal{G}$ on more than $1/2+\varepsilon$ fraction of inputs for $$ s = o \! \left ( \frac{n^2}{ \left(k \cdot 4^k \cdot {R}^{(k)}(\mathcal{G}) \cdot \log (n/\varepsilon) \cdot \log(1/\varepsilon) \right)^{2}} \right).$$ As a corollary, we get an average-case lower bound for $GIP^k_n$ against $FORMULA[n^{1.99}]\circ PTF^{k-1}$. (2) There is a PRG of seed length $n/2 + O\left(\sqrt{s} \cdot R^{(2)}(\mathcal{G}) \cdot\log(s/\varepsilon) \cdot \log (1/\varepsilon) \right)$ that $\varepsilon$-fools $FORMULA[s] \circ \mathcal{G}$. For $FORMULA[s] \circ LTF$, we get the better seed length $O\left(n^{1/2}\cdot s^{1/4}\cdot \log(n)\cdot \log(n/\varepsilon)\right)$. This gives the first non-trivial PRG (with seed length $o(n)$) for intersections of $n$ half-spaces in the regime where $\varepsilon \leq 1/n$. (3) There is a randomized $2^{n-t}$-time $\#$SAT algorithm for $FORMULA[s] \circ \mathcal{G}$, where $$t=Ω\left(\frac{n}{\sqrt{s}\cdot\log^2(s)\cdot R^{(2)}(\mathcal{G})}\right)^{1/2}.$$ In particular, this implies a nontrivial #SAT algorithm for $FORMULA[n^{1.99}]\circ LTF$. (4) The Minimum Circuit Size Problem is not in $FORMULA[n^{1.99}]\circ XOR$. On the algorithmic side, we show that $FORMULA[n^{1.99}] \circ XOR$ can be PAC-learned in time $2^{O(n/\log n)}$.
