文章基本信息
- 标题：Algorithms and Lower Bounds for De Morgan Formulas of Low-Communication Leaf Gates
- 本地全文：下载
- 作者：Valentine Kabanets ; Sajin Koroth ; Zhenjian Lu 等
- 期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
- 电子版ISSN：1868-8969
- 出版年度：2020
- 卷号：169
- 页码：15:1-15:41
- DOI：10.4230/LIPIcs.CCC.2020.15
- 出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
- 摘要：The class ð-¥ð-®ð-±ð-¬ð-´ð-«ð- [s]â^~ð'¢ consists of Boolean functions computable by size-s de Morgan formulas whose leaves are any Boolean functions from a class ð'¢. We give lower bounds and (SAT, Learning, and PRG) algorithms for FORMULA[n^{1.99}]â^~ð'¢, for classes ð'¢ of functions with low communication complexity. Let R^(k)(ð'¢) be the maximum k-party number-on-forehead randomized communication complexity of a function in ð'¢. Among other results, we show that: - The Generalized Inner Product function ð-¦ð-¨ð-¯^k_n cannot be computed in ð-¥ð-®ð-±ð-¬ð-´ð-«ð- [s]â^~ð'¢ on more than 1/2+ε fraction of inputs for s = o(n²/{(kâ<.4^kâ<.R^(k)(ð'¢)â<.log (n/ε)â<.log(1/ε))²}). This significantly extends the lower bounds against bipartite formulas obtained by [Avishay Tal, 2017]. As a corollary, we get an average-case lower bound for ð-¦ð-¨ð-¯^k_n against ð-¥ð-®ð-±ð-¬ð-´ð-«ð- [n^{1.99}]â^~ð-¯ð-³ð-¥^{k-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 n/2 + O(â^Ssâ<.R^(2)(ð'¢)â<.log(s/ε)â<.log(1/ε)) that ε-fools FORMULA[s]â^~ð'¢. For the special case of FORMULA[s]â^~ð-«ð-³ð-¥, i.e., size-s formulas with LTF (linear threshold function) gates at the bottom, we get the better seed length O(n^{1/2}â<.s^{1/4}â<.log(n)â<.log(n/ε)). 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 [Ryan O'Donnell et al., 2019]. - There exists a randomized 2^{n-t}-time #SAT algorithm for ð-¥ð-®ð-±ð-¬ð-´ð-«ð- [s]â^~ð'¢, where t = Ω(n/{â^Ssâ<.log²(s)â<.R^(2)(ð'¢)})^{1/2}. In particular, this implies a nontrivial #SAT algorithm for ð-¥ð-®ð-±ð-¬ð-´ð-«ð- [n^1.99]â^~ð-«ð-³ð-¥. - The Minimum Circuit Size Problem is not in ð-¥ð-®ð-±ð-¬ð-´ð-«ð- [n^1.99]â^~ð-·ð-®ð-±; thereby making progress on hardness magnification, in connection with results from [Igor Carboni Oliveira et al., 2019; Lijie Chen et al., 2019]. On the algorithmic side, we show that the concept class ð-¥ð-®ð-±ð-¬ð-´ð-«ð- [n^1.99]â^~ð-·ð-®ð-± can be PAC-learned in time 2^O(n/log n).
- 关键词：de Morgan formulas; circuit lower bounds; satisfiability (SAT); pseudorandom generators (PRGs); learning; communication complexity; polynomial threshold functions (PTFs); parities
