Algorithms and lower bounds for De Morgan formulas of low-communication leaf gates

DOI10.1145/3470861MaRDI QIDQ5066142zbMATH OpenOpenAlexWikidataFDO

Authors Valentine Kabanets, Sajin Koroth, Zhenjian Lu, Dimitrios Myrisiotis, Igor C. Oliveira

Publication date 29 March 2022

Published in ACM Transactions on Computation Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2002.08533

zbMATH Keywords

learningsatisfiabilitycommunication complexitypseudorandom generatorsDe Morgan formulasparitiescircuit lower bounds

Mathematics Subject Classification ID

Randomized algorithms (68W20) Networks and circuits as models of computation; circuit complexity (68Q06) Communication complexity, information complexity (68Q11)

Abstract: The class $FORMULA[s]circmathcalG$ consists of Boolean functions computable by size-$s$ de Morgan formulas whose leaves are any Boolean functions from a class $mathcalG$. We give lower bounds and (SAT, Learning, and PRG) algorithms for $FORMULA[n^{1.99}]circmathcalG$, for classes $mathcalG$ of functions with low communication complexity. Let $R^{(k)}(mathcalG)$ be the maximum $k$-party NOF randomized communication complexity of $mathcalG$. We show: (1) The Generalized Inner Product function $GI{P}_n^k$ cannot be computed in $FORMULA[s]circmathcalG$ on more than $1/2+varepsilon$ fraction of inputs for ${\displaystyle }$ s = o ! left ( frac{n^2}{ left(k cdot 4^k cdot {R}^{(k)}(mathcal{G}) cdot log (n/varepsilon) cdot log(1/varepsilon) ight)^{2}} ight).${\displaystyle }$ As a corollary, we get an average-case lower bound for $GI{P}_n^k$ against $FORMULA[n^{1.99}]circPT{F}^{k-1}$. (2) There is a PRG of seed length $n/2+Oleft(sqrtscdot{R}^{(2)}(mathcalG)cdotlog(s/varepsilon)cdotlog(1/varepsilon)ight)$ that $varepsilon$-fools $FORMULA[s]circmathcalG$. For $FORMULA[s]circLTF$, we get the better seed length $Oleft(n^{1/2}cdot{s}^{1/4}cdotlog(n)cdotlog(n/varepsilon)ight)$. This gives the first non-trivial PRG (with seed length $o(n)$) for intersections of $n$ half-spaces in the regime where $varepsilonleq1/n$. (3) There is a randomized $2^{n-t}$-time $$SAT algorithm for $FORMULA[s]circmathcalG$, where ${\displaystyle }$t=Omegaleft(frac{n}{sqrt{s}cdotlog^2(s)cdot R^{(2)}(mathcal{G})} ight)^{1/2}.${\displaystyle }$ In particular, this implies a nontrivial #SAT algorithm for $FORMULA[n^{1.99}]circLTF$. (4) The Minimum Circuit Size Problem is not in $FORMULA[n^{1.99}]circXOR$. On the algorithmic side, we show that $FORMULA[n^{1.99}]circXOR$ can be PAC-learned in time $2^{O(n/logn)}$.

Recommendations

• Algorithms and lower bounds for De Morgan formulas of low-communication leaf gates
• Formula lower bounds via the quantum method
• Shrinkage of de Morgan formulae under restriction
• Circuit lower bounds for MCSP from local pseudorandom generators
• Average-case lower bounds for formula size

Cited in

(1)

• Algorithms and lower bounds for De Morgan formulas of low-communication leaf gates

This page was built for publication: Algorithms and lower bounds for De Morgan formulas of low-communication leaf gates

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5066142)