ECCC - Reportshttps://eccc.weizmann.ac.il/Latest Reports published at https://eccc.weizmann.ac.ilen-usTue, 19 Feb 2019 20:24:23 +0200TR19-021 | $AC^0[p]$ Lower Bounds and NP-Hardness for Variants of MCSP |
Rahul Ilango
https://eccc.weizmann.ac.il/report/2019/021The Minimum Circuit Size Problem (MCSP) asks whether a (given) Boolean function has a circuit of at most a (given) size. Despite over a half-century of study, we know relatively little about the computational complexity of MCSP. We do know that questions about the complexity of MCSP have significant ramifications on longstanding open problems. In a recent development, Golovnev et al. [11] improves the status of unconditional lower bounds for MCSP, showing that MCSP is not in $AC^0[p]$ for any prime $p$. While their results generalize to most "typical" circuit classes, it fails to generalize to the circuit minimization problem for depth-d formulas, denoted ($AC^0_d$)-MCSP. In particular, their result relies on a Lipchitz hypothesis that is unknown (and possibly false) in the case of ($AC^0_d$)-MCSP. Despite this, we show that ($AC^0_d$)-MCSP is not in $AC^0[p]$ by proving even the failure of the Lipchitzness for $AC^0_d$ formulas implies that MAJORITY reduces to ($AC^0_d$)-MCSP under $AC^0$ truth table reductions. Somewhat remarkably, our proof (in the case of non-Lipchitzness) uses completely different techniques than [11]. To our knowledge, this is the first MCSP reduction that uses modular properties of a function's circuit complexity.
We also define MOCSP, an oracle version of MCSP that takes as input a Boolean function $f$, a size threshold $s$, and oracle Boolean functions $f_1, ..., f_t$, and determines whether there is an oracle circuit of size at most $s$ that computes $f$ when given access to $f_1, ... , f_t$. We prove that MOCSP is $NP$-complete under non-uniform $AC^0$ many-one reductions as well as (uniform) $ZPP$ truth table reductions. We also observe that improving this $ZPP$ reduction to a deterministic polynomial-time reduction requires showing $EXP \neq ZPP$ (using theorems of Hitchcock and Pavan [17] and Murray and Williams [22]). Optimistically, these MOCSP results could be a first step towards $NP$-hardness results for MCSP. At the very least, we believe MOCSP clarifies the barriers towards proving hardness for MCSP and provides a useful "testing ground" for questions about MCSP.Tue, 19 Feb 2019 20:24:23 +0200https://eccc.weizmann.ac.il/report/2019/021TR19-020 | On Tseitin formulas, read-once branching programs and treewidth |
Ludmila Glinskih,
Dmitry Itsykson
https://eccc.weizmann.ac.il/report/2019/020We show that any nondeterministic read-once branching program that computes a satisfiable Tseitin formula based on an $n\times n$ grid graph has size at least $2^{\Omega(n)}$. Then using the Excluded Grid Theorem by Robertson and Seymour we show that for arbitrary graph $G(V,E)$ any nondeterministic read-once branching program that computes a satisfiable Tseitin formula based on $G$ has size at least $2^{\Omega(tw(G)^\delta)}$ for all $\delta <1/36$, where $tw(G)$ is the treewidth of $G$ (for planar graphs and some other classes of graphs the statement holds for $\delta=1$). We also show an upper bound $O(|E| 2^{pw(G)})$, where $pw(G)$ is the pathwidth of $G$.
We apply the mentioned results in the analysis of the complexity of derivation in the proof system $OBDD(\land, reordering)$ and show that any $OBDD(\land, reordering)$-refutation of an unsatisfiable Tseitin formula based on a graph $G$ has size at least $2^{\Omega(tw(G)^\delta)}$.Tue, 19 Feb 2019 20:23:06 +0200https://eccc.weizmann.ac.il/report/2019/020TR19-019 | Towards Optimal Depth Reductions for Syntactically Multilinear Circuits |
Mrinal Kumar,
Rafael Mendes de Oliveira,
Ramprasad Saptharishi
https://eccc.weizmann.ac.il/report/2019/019We show that any $n$-variate polynomial computable by a syntactically multilinear circuit of size $\mathop{poly}(n)$ can be computed by a depth-$4$ syntactically multilinear ($\Sigma\Pi\Sigma\Pi$) circuit of size at most $\exp\left({O\left(\sqrt{n\log n}\right)}\right)$. For degree $d = \omega(n/\log n)$, this improves upon the upper bound of $\exp\left({O(\sqrt{d}\log n)}\right)$ obtained by Tavenas (MFCS 2015) for general circuits, and is known to be asymptotically optimal in the exponent when $d < n^{\epsilon}$ for a small enough constant $\epsilon$. Our upper bound matches the lower bound of $\exp\left({\Omega\left(\sqrt{n\log n}\right)}\right)$ proved by Raz and Yehudayoff (CC 2009), and thus cannot be improved further in the exponent. Our results hold over all fields and also generalize to circuits of small individual degree.
More generally, we show that an $n$-variate polynomial computable by a syntactically multilinear circuit of size $\mathop{poly}(n)$ can be computed by a syntactically multilinear circuit of product-depth $\Delta$ of size at most $\exp\left(O\left(\Delta \cdot (n/\log n)^{1/\Delta} \cdot \log n\right)\right)$. It follows from the lower bounds of Raz and Yehudayoff (CC 2009) that in general, for constant $\Delta$, the exponent in this upper bound is tight and cannot be improved to $o\left(\left(n/\log n\right)^{1/\Delta}\cdot \log n\right)$.
Tue, 19 Feb 2019 16:27:13 +0200https://eccc.weizmann.ac.il/report/2019/019TR19-018 | AC0[p] Lower Bounds against MCSP via the Coin Problem |
Valentine Kabanets,
Alexander Golovnev,
Rahul Ilango,
Russell Impagliazzo,
Antonina Kolokolova,
Avishay Tal
https://eccc.weizmann.ac.il/report/2019/018Minimum Circuit Size Problem (MCSP) asks to decide if a given truth table of an $n$-variate boolean function has circuit complexity less than a given parameter $s$. We prove that MCSP is hard for constant-depth circuits with mod $p$ gates, for any prime $p\geq 2$ (the circuit class $AC^0[p])$. Namely, we show that MCSP requires $d$-depth $AC^0[p]$ circuits of size at least $exp(N^{0.49/d})$, where $N=2^n$ is the size of an input truth table of an $n$-variate boolean function. Our circuit lower bound proof shows that MCSP can solve the coin problem: distinguish uniformly random $N$-bit strings from those generated using independent samples from a biased random coin which is $1$ with probability $1/2+N^{-0.49}$, and $0$ otherwise. Solving the coin problem with such parameters is known to require exponentially large $AC^0[p]$ circuits. Moreover, this also implies that MAJORITY is computable by a non-uniform $AC^0$ circuit of polynomial size that also has MCSP-oracle gates. The latter has a few other consequences for the complexity of MCSP, e.g., we get that any boolean function in $NC^1$ (i.e., computable by a polynomial-size formula) can also be computed by a non-uniform polynomial-size $AC^0$ circuit with MCSP-oracle gates.Mon, 18 Feb 2019 23:30:49 +0200https://eccc.weizmann.ac.il/report/2019/018TR19-017 | Fourier bounds and pseudorandom generators for product tests |
Chin Ho Lee
https://eccc.weizmann.ac.il/report/2019/017 We study the Fourier spectrum of functions $f\colon \{0,1\}^{mk} \to \{-1,0,1\}$ which can be written as a product of $k$ Boolean functions $f_i$ on disjoint $m$-bit inputs. We prove that for every positive integer $d$,
\[
\sum_{S \subseteq [mk]: |S|=d} |\hat{f_S}| = O(m)^d .
\]
Our upper bound is tight up to a constant factor in the $O(\cdot)$. Our proof builds on a new "level-$d$ inequality" that bounds above $\sum_{|S|=d} \hat{f_S}^2$ for any $[0,1]$-valued function $f$ in terms of its expectation, which may be of independent interest.
As a result, we construct pseudorandom generators for such functions with seed length $\tilde O(m + \log(k/\varepsilon))$, which is optimal up to polynomial factors in $\log m$, $\log\log k$ and $\log\log(1/\varepsilon)$. Our generator in particular works for the well-studied class of combinatorial rectangles, where in addition we allow the bits to be read in any order. Even for this special case, previous generators have an extra $\tilde O(\log(1/\varepsilon))$ factor in their seed lengths.
Using Schur-convexity, we also extend our results to functions $f_i$ whose range is $[-1,1]$.
Thu, 07 Feb 2019 16:59:22 +0200https://eccc.weizmann.ac.il/report/2019/017TR19-016 | The hardest halfspace |
Alexander A. Sherstov
https://eccc.weizmann.ac.il/report/2019/016We study the approximation of halfspaces $h:\{0,1\}^n\to\{0,1\}$ in the infinity norm by polynomials and rational functions of any given degree. Our main result is an explicit construction of the "hardest" halfspace, for which we prove polynomial and rational approximation lower bounds that match the trivial upper bounds achievable for all halfspaces. This completes a lengthy line of work started by Myhill and Kautz (1961).
As an application, we construct a communication problem with essentially the largest possible gap, of $n$ versus $2^{-\Omega(n)},$ between the sign-rank and discrepancy. Equivalently, our problem exhibits a gap of $\log n$ versus $\Omega(n)$ between the communication complexity with unbounded versus weakly unbounded error, improving quadratically on previous constructions and completing a line of work started by Babai, Frankl, and Simon (FOCS 1986). Our results further generalize to the $k$-party number-on-the-forehead model, where we obtain an explicit separation of $\log n$ versus $\Omega(n/4^{n})$ for communication with unbounded versus weakly unbounded error. This gap is a quadratic improvement on previous work and matches the state of the art for number-on-the-forehead lower bounds.Thu, 07 Feb 2019 16:57:13 +0200https://eccc.weizmann.ac.il/report/2019/016TR19-015 | QMA Lower Bounds for Approximate Counting |
William Kretschmer
https://eccc.weizmann.ac.il/report/2019/015We prove a query complexity lower bound for $QMA$ protocols that solve approximate counting: estimating the size of a set given a membership oracle. This gives rise to an oracle $A$ such that $SBP^A \not\subset QMA^A$, resolving an open problem of Aaronson [2]. Our proof uses the polynomial method to derive a lower bound for the $SBQP$ query complexity of the $AND$ of two approximate counting instances. We use Laurent polynomials as a tool in our proof, showing that the "Laurent polynomial method" can be useful even for problems involving ordinary polynomials.Thu, 07 Feb 2019 10:16:08 +0200https://eccc.weizmann.ac.il/report/2019/015TR19-014 | A New Proof of Nonsignalling Multiprover Parallel Repetition Theorem |
Himanshu Tyagi,
Shun Watanabe
https://eccc.weizmann.ac.il/report/2019/014We present an information theoretic proof of the nonsignalling multiprover parallel repetition theorem, a recent extension of its two-prover variant that underlies many hardness of approximation results. The original proofs used de Finetti type decomposition for strategies. We present a new proof that is based on a technique we introduced recently for proving strong converse results in multiuser information theory and entails a change of measure after replacing hard information constraints with soft ones.Sun, 03 Feb 2019 14:39:00 +0200https://eccc.weizmann.ac.il/report/2019/014TR19-013 | CSPs with Global Modular Constraints: Algorithms and Hardness via Polynomial Representations |
Joshua Brakensiek,
Sivakanth Gopi,
Venkatesan Guruswami
https://eccc.weizmann.ac.il/report/2019/013We study the complexity of Boolean constraint satisfaction problems (CSPs) when the assignment must have Hamming weight in some congruence class modulo $M$, for various choices of the modulus $M$. Due to the known classification of tractable Boolean CSPs, this mainly reduces to the study of three cases: 2SAT, HornSAT, and LIN-MOD2 (linear equations mod $2$). We classify the moduli $M$ for which these respective problems are polynomial time solvable, and when they are not (assuming the ETH). Our study reveals that this modular constraint lends a surprising richness to these classic, well-studied problems, with interesting broader connections to complexity theory and coding theory. The HornSAT case is connected to the covering complexity of polynomials representing the NAND function mod $M$. The LIN-MOD2 case is tied to the sparsity of polynomials representing the OR function mod $M$, which in turn has connections to modular weight distribution properties of linear codes and locally decodable codes. In both cases, the analysis of our algorithm as well as the hardness reduction rely on these polynomial representations, highlighting an interesting algebraic common ground between hard cases for our algorithms and the gadgets which show hardness. These new complexity measures of polynomial representations merit further study.
The inspiration for our study comes from a recent work by NĂ¤gele, Sudakov, and Zenklusen on submodular minimization with a global congruence constraint. Our algorithm for HornSAT has strong similarities to their algorithm, and in particular identical kind of set systems arise in both cases. Our connection to polynomial representations leads to a simpler analysis of such set systems, and also sheds light on (but does not resolve) the complexity of submodular minimization with a congruency requirement modulo a composite $M$.Thu, 31 Jan 2019 17:15:39 +0200https://eccc.weizmann.ac.il/report/2019/013TR19-012 | Multi-pseudodeterministic algorithms |
Oded Goldreich
https://eccc.weizmann.ac.il/report/2019/012In this work, dedicated to Shafi Goldwasser, we consider a relaxation of the notion of pseudodeterministic algorithms, which was put forward by Gat and Goldwasser ({\em ECCC}, TR11--136, 2011).
Pseudodeterministic algorithms are randomized algorithms that solve search problems by almost always providing the same canonical solution (per each input).
Multi-pseudodeterministic algorithms relax the former notion by allowing the algorithms to output one of a bounded number of canonical solutions (per each input).
We show that efficient multi-seudodeterministic algorithms can solve natural problems that are not solveable by efficient pseudodeterministic algorithms, present a composition theorem regarding multi-pseudodeterministic algorithms,
and relate them to other known notions.
Sun, 27 Jan 2019 19:25:14 +0200https://eccc.weizmann.ac.il/report/2019/012