Algorithms and lower bounds for de morgan formulas of low-communication leaf gates
Algorithms and lower bounds for de morgan formulas of low-communication leaf gates
复制标题
低通信叶门德摩根公式的算法和下界
DOI：
--
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
I. Oliveira
中科院分区：
文献类型：
--
作者：
Valentine Kabanets;Sajin Koroth;Zhenjian Lu;Dimitrios Myrisiotis;I. Oliveira
类FORMULA[s] ο G由可由size-s de Morgan公式计算的布尔函数组成，这些公式的叶是来自类G的任何布尔函数。对于具有低通信复杂度的函数G类，我们给出了FORMULA[n1.99] ο G的下界和（SAT， Learning和PRG）算法。设R(k) (G)为G中函数的最大k方额上随机通信复杂度。在其他结果中，我们表明：•对于[MATH HERE]，广义内积函数GIPkn不能在大于1/2 + ε分数的输入上用公式[s] ο G计算，这显著地扩展了由[61]得到的二部公式的下界。作为推论，我们得到了GIPkn对FORMULA[n1.99] ο PTFk-1的平均情况下界，即底部有次-(k -1)次PTF（多项式阈值函数）门的次二次大小的de Morgan公式。•有一个种子长度的PRG [MATH HERE] ε-fool FORMULA[s] ο G.对于FORMULA[s] οLTF的特殊情况，即底部有LTF（线性阈值函数）门的size-s公式，我们得到了更好的种子长度[MATH HERE]。特别地，这提供了第一个非平凡PRG（种子长度为o(n)），对于ε≤1/n的区域中n个半空间的交集，补充了最近的结果[44]。•对于FORMULA[n1.99] ο LTF，存在一个随机的2n-t时间#SAT算法，其中[MATH HERE]特别地，这意味着一个非平凡的#SAT算法。•最小电路尺寸问题不在公式[n1.99] ο XOR中；从而在硬度放大方面取得进展，这与[45,12]的结果有关。在算法方面，我们证明了概念类FORMULA[n1.99] ο XOR可以在20 （n/log n）时间内进行pac学习。
The class FORMULA[s] ο G consists of Boolean functions computable by size-s de Morgan formulas whose leaves are any Boolean functions from a class G. We give lower bounds and (SAT, Learning, and PRG) algorithms for FORMULA[n1.99] ο G, for classes G of functions with low communication complexity. Let R(k) (G) be the maximum k-party number-on-forehead randomized communication complexity of a function in G. Among other results, we show that: • The Generalized Inner Product function GIPkn cannot be computed in FORMULA[s] ο G on more than 1/2 + ε fraction of inputs for [MATH HERE] This significantly extends the lower bounds against bipartite formulas obtained by [61]. As a corollary, we get an average-case lower bound for GIPkn against FORMULA[n1.99] ο PTFk-1, i.e., sub-quadratic-size de Morgan formulas with degree-(k - 1) PTF (polynomial threshold function) gates at the bottom. • There is a PRG of seed length [MATH HERE] that ε-fools FORMULA[s] ο G. For the special case of FORMULA[s] οLTF, i.e., size-s formulas with LTF (linear threshold function) gates at the bottom, we get the better seed length [MATH HERE]. In particular, this provides the first non-trivial PRG (with seed length o(n)) for intersections of n half-spaces in the regime where ε ≤ 1/n, complementing a recent result of [44]. • There exists a randomized 2n-t-time #SAT algorithm for FORMULA[s] ο G, where [MATH HERE] In particular, this implies a nontrivial #SAT algorithm for FORMULA[n1.99] ο LTF. • The Minimum Circuit Size Problem is not in FORMULA[n1.99] ο XOR; thereby making progress on hardness magnification, in connection with results from [45, 12]. On the algorithmic side, we show that the concept class FORMULA[n1.99] ο XOR can be PAC-learned in time 2o(n/log n).
影响因子：
1.4
作者：
Göös, Mika;Pitassi, Toniann;Watson, Thomas
通讯作者：
Watson, Thomas
来自本地伪随机发生器的 MCSP 电路下界
影响因子：
0.7
作者：
Cheraghchi M
通讯作者：
Cheraghchi M