ECCC - Reportshttps://example.com/Latest Reports published at https://eccc.weizmann.ac.ilen-usMon, 23 Oct 2017 19:05:30 +0300TR17-158 | Minimum Circuit Size, Graph Isomorphism, and Related Problems |
Eric Allender,
Joshua Grochow,
Dieter van Melkebeek,
Cris Moore,
Andrew Morgan
https://eccc.weizmann.ac.il/report/2017/158We study the computational power of deciding whether a given truth-table can be described by a circuit of a given size (the Minimum Circuit Size Problem, or MCSP for short), and of the variant denoted as MKTP where circuit size is replaced by a polynomially-related Kolmogorov measure. All prior reductions from supposedly-intractable problems to MCSP / MKTP hinged on the power of MCSP / MKTP to distinguish random distributions from distributions produced by hardness-based pseudorandom generator constructions. We develop a fundamentally different approach inspired by the well-known interactive proof system for the complement of Graph Isomorphism (GI). It yields a randomized reduction with zero-sided error from GI to MKTP. We generalize the result and show that GI can be replaced by any isomorphism problem for which the underlying group satisfies some elementary properties. Instantiations include Linear Code Equivalence, Permutation Group Conjugacy, and Matrix Subspace Conjugacy. Along the way we develop encodings of isomorphism classes that are efficiently decodable and achieve compression that is at or near the information-theoretic optimum; those encodings may be of independent interest.Mon, 23 Oct 2017 19:05:30 +0300https://eccc.weizmann.ac.il/report/2017/158TR17-157 | High Degree Sum of Squares Proofs, Bienstock-Zuckerberg hierarchy and Chvatal-Gomory cuts |
Monaldo Mastrolilli
https://eccc.weizmann.ac.il/report/2017/157Chvatal-Gomory (CG) cuts and the Bienstock-Zuckerberg hierarchy capture useful linear programs that the standard bounded degree Lasserre/Sum-of-Squares (SOS) hierarchy fails to capture.
In this paper we present a novel polynomial time SOS hierarchy for 0/1 problems with a custom subspace of high degree polynomials (not the standard subspace of low-degree polynomials). We show that the new SOS hierarchy recovers the Bienstock-Zuckerberg hierarchy. Our result implies a linear program that reproduces the Bienstock-Zuckerberg hierarchy as a polynomial sized, efficiently constructible extended formulation that satisfies all constant pitch inequalities. The construction is also very simple, and it is fully defined by giving the supporting polynomials (one paragraph). Moreover, for a class of polytopes (e.g. set covering and packing problems) it optimizes, up to an arbitrarily small error, over the polytope resulting from any constant rounds of CG cuts.
Arguably, this is the first example where different basis functions can be useful in asymmetric situations to obtain a hierarchy of relaxations.
Sun, 15 Oct 2017 18:23:33 +0300https://eccc.weizmann.ac.il/report/2017/157TR17-156 | Small-depth Multilinear Formula Lower Bounds for Iterated Matrix Multiplication, with Applications |
Suryajith Chillara,
Nutan Limaye,
Srikanth Srinivasan
https://eccc.weizmann.ac.il/report/2017/156The complexity of Iterated Matrix Multiplication is a central theme in Computational Complexity theory, as the problem is closely related to the problem of separating various complexity classes within $\mathrm{P}$. In this paper, we study the algebraic formula complexity of multiplying $d$ many $2\times 2$ matrices, denoted $\mathrm{IMM}_{d}$, and show that the well-known divide-and-conquer algorithm cannot be significantly improved at any depth, as long as the formulas are multilinear.
Formally, for each depth $\Delta \leq \log d$, we show that any product-depth $\Delta$ multilinear formula for $\mathrm{IMM}_d$ must have size $\exp(\Omega(\Delta d^{1/\Delta})).$ It also follows from this that any multilinear circuit of product-depth $\Delta$ for the same polynomial of the above form must have a size of $\exp(\Omega(d^{1/\Delta})).$ In particular, any polynomial-sized multilinear formula for $\mathrm{IMM}_d$ must have depth $\Omega(\log d)$, and any polynomial-sized multilinear circuit for $\mathrm{IMM}_d$ must have depth $\Omega(\log d/\log \log d).$ Both these bounds are tight up to constant factors.
Our lower bound has the following consequences for multilinear formula complexity.
1. Depth-reduction: A well-known result of Brent (JACM 1974) implies that any formula of size $s$ can be converted to one of size $s^{O(1)}$ and depth $O(\log s)$; further, this reduction continues to hold for multilinear formulas. On the other hand, our lower bound implies that any depth-reduction in the multilinear setting cannot reduce the depth to $o(\log s)$ without a superpolynomial blow-up in size.
2. Separations from general formulas: Shpilka and Yehudayoff (FnTTCS 2010) asked whether general formulas can be more efficient than multilinear formulas for computing multilinear polynomials. Our result, along with a non-trivial upper bound for $\mathrm{IMM}_{d}$ implied by a result of Gupta, Kamath, Kayal and Saptharishi (SICOMP 2016), shows that for any size $s$ and product-depth $\Delta = o(\log s),$ general formulas of size $s$ and product-depth $\Delta$ cannot be converted to multilinear formulas of size $s^{\omega(1)}$ and product-depth $\Delta,$ when the underlying field has characteristic zero.
Sun, 15 Oct 2017 17:30:24 +0300https://eccc.weizmann.ac.il/report/2017/156TR17-155 | Proofs of Proximity for Distribution Testing |
Alessandro Chiesa,
Tom Gur
https://eccc.weizmann.ac.il/report/2017/155Distribution testing is an area of property testing that studies algorithms that receive few samples from a probability distribution D and decide whether D has a certain property or is far (in total variation distance) from all distributions with that property. Most natural properties of distributions, however, require a large number of samples to test, which motivates the question of whether there are natural settings wherein fewer samples suffice.
We initiate a study of proofs of proximity for properties of distributions. In their basic form, these proof systems consist of a tester that not only has sample access to a distribution but also explicit access to a proof string that depends on the distribution. We refer to these as NP distribution testers, or MA distribution testers if the tester is a probabilistic algorithm. We also study the more general notion of IP distribution testers, in which the tester interacts with an all-powerful untrusted prover.
We investigate the power and limitations of proofs of proximity for distributions and chart a landscape that, surprisingly, is significantly different from that of proofs of proximity for functions. Our main results include showing that MA distribution testers can be quadratically stronger than standard distribution testers, but no stronger than that; in contrast, IP distribution testers can be exponentially stronger than standard distribution testers, but when restricted to public coins they can be at best quadratically stronger.Fri, 13 Oct 2017 12:24:00 +0300https://eccc.weizmann.ac.il/report/2017/155TR17-154 | The Relation between Polynomial Calculus, Sherali-Adams, and Sum-of-Squares Proofs |
Christoph Berkholz
https://eccc.weizmann.ac.il/report/2017/154We relate different approaches for proving the unsatisfiability of a system of real polynomial equations over Boolean variables. On the one hand, there are the static proof systems Sherali-Adams and sum-of-squares (a.k.a. Lasserre), which are based on linear and semi-definite programming relaxations. On the other hand, we consider polynomial calculus, which is a dynamic algebraic proof system that models Gröbner basis computations.
Our first result is that sum-of-squares simulates polynomial calculus: any polynomial calculus refutation of degree $d$ can be transformed into a sum-of-squares refutation of degree $2d$ and only polynomial increase in size. In contrast, our second result shows that this is not the case for Sherali-Adams: there are systems of polynomial equations that have polynomial calculus refutations of degree $3$ and polynomial size, but require Sherali-Adams refutations of degree $\Omega(\sqrt{n}/\log n)$ and exponential size.Thu, 12 Oct 2017 14:55:10 +0300https://eccc.weizmann.ac.il/report/2017/154TR17-153 | Discovering the roots: Uniform closure results for algebraic classes under factoring |
Pranjal Dutta,
Nitin Saxena,
Amit Sinhababu
https://eccc.weizmann.ac.il/report/2017/153Newton iteration (NI) is an almost 350 years old recursive formula that approximates a simple root of a polynomial quite rapidly. We generalize it to a matrix recurrence (allRootsNI) that approximates all the roots simultaneously. In this form, the process yields a better circuit complexity in the case when the number of roots $r$ is small but the multiplicities are exponentially large. Our method sets up a linear system in $r$ unknowns and iteratively builds the roots as formal power series. For an algebraic circuit $f(x_1,\ldots,x_n)$ of size $s$ we prove that each factor has size at most a polynomial in: $s$ and the degree of the squarefree part of $f$. Consequently, if $f_1$ is a $2^{\Omega(n)}$-hard polynomial then any nonzero multiple $\prod_{i} f_i^{e_i}$ is equally hard for arbitrary positive $e_i$'s, assuming that $\sum_i\deg(f_i)$ is at most $2^{O(n)}$.
It is an old open question whether the class of poly($n$)-sized formulas (resp. algebraic branching programs) is closed under factoring. We show that given a polynomial $f$ of degree $n^{O(1)}$ and formula (resp. ABP) size $n^{O(\log n)}$ we can find a similar size formula (resp. ABP) factor in randomized poly($n^{\log n}$)-time.
Consequently, if determinant requires $n^{\Omega(\log n)}$ size formula, then the same can be said about any of its nonzero multiples.
As part of our proofs, we identify a new property of multivariate polynomial factorization. We show that under a random linear transformation $\tau$, $f(\tau\overline{x})$ completely factors via power series roots. Moreover, the factorization adapts well to circuit complexity analysis. This with allRootsNI are the techniques that help us make progress towards the old open problems; supplementing the large body of classical results and concepts in algebraic circuit factorization (eg.~Zassenhaus, J.NT 1969; Kaltofen, STOC 1985-7 \& B\"urgisser, FOCS 2001).
Wed, 11 Oct 2017 23:39:17 +0300https://eccc.weizmann.ac.il/report/2017/153TR17-152 | One-way Communication and Non-adaptive Decision Tree |
Swagato Sanyal
https://eccc.weizmann.ac.il/report/2017/152Let $f$ be a Boolean function on $n$-bits, and $\mathsf{IP}$ the inner-product function on $2b$ bits. Let $f^{\mathsf{IP}}:=f \circ \mathsf{IP}^n$ be the two party function obtained by composing $f$ with $\mathsf{IP}$. In this work we bound the one-way communication complexity of $f^{\IP}$ in terms of the non-adaptive query complexity of $f$, from below. Similar results are known for general communication protocols and adaptive decision trees, when the arity of the inner function (inner-product in our case) is at least logarithmic in $n$. We prove analogous results for one-way communication as long as $b$ is a large enough constant. Let $\sR_{\cc, \epsilon}^{\rightarrow}(\cdot)$ and $\sD_{\cc}^\rightarrow(\cdot)$ denote the randomized $\epsilon$-error and deterministic one-way communication complexity respectively. Let $\sD_{\dt}^\rightarrow(\cdot)$ denote the deterministic non-adaptive query complexity. Let $\rH_{\bin}(\cdot)$ denote the binary entropy function. We prove that
\begin{itemize}
\item If $f$ is a \emph{total} Boolean function and $b \geq 2$, then $\sR^{\rightarrow}_{\cc, \epsilon}(f^{\mathsf{IP}}) \geq (1-\rH_{\bin}(\epsilon))n(b-1)$.
\item If $f$ is a partial Boolean function and $b \geq 4$, then $\sD_{\cc}^\rightarrow(f^{\mathsf{IP}})=\Omega(b \cdot \sD_{\dt}^\rightarrow(f))$.
\end{itemize}Wed, 11 Oct 2017 19:20:02 +0300https://eccc.weizmann.ac.il/report/2017/152TR17-151 | Stabbing Planes |
Noah Fleming,
Paul Beame,
Russell Impagliazzo,
Robert Robere,
Antonina Kolokolova,
Toniann Pitassi,
Denis Pankratov
https://eccc.weizmann.ac.il/report/2017/151We introduce and develop a new semi-algebraic proof system, called Stabbing Planes that is in the style of DPLL-based modern SAT solvers. As with DPLL, there is only one rule: the current polytope can be subdivided by
branching on an inequality and its "integer negation.'' That is, we can (nondeterministically choose) a hyperplane a x \geq b with integer coefficients, which partitions the polytope into three pieces: the points in the polytope satisfying a x \geq b, the points satisfying a x \leq b-1, and the middle slab b-1 < a x < b. Since the middle slab contains no integer points it can be safely discarded, and the algorithm proceeds recursively on the other two branches. Each path terminates when the current polytope is empty, which is polynomial-time checkable. Among our results, we show somewhat surprisingly that Stabbing Planes can efficiently simulate Cutting Planes, and moreover, is strictly stronger than Cutting Planes under a reasonable conjecture. We prove linear lower bounds on the rank of Stabbing Planes refutations, by adapting a lifting argument in communication complexity.Mon, 09 Oct 2017 02:20:35 +0300https://eccc.weizmann.ac.il/report/2017/151TR17-150 | All Classical Adversary Methods are Equivalent for Total Functions |
Andris Ambainis,
Martins Kokainis,
Krisjanis Prusis,
Jevgenijs Vihrovs
https://eccc.weizmann.ac.il/report/2017/150We show that all known classical adversary lower bounds on randomized query complexity are equivalent for total functions, and are equal to the fractional block sensitivity $\text{fbs}(f)$. That includes the Kolmogorov complexity bound of Laplante and Magniez and the earlier relational adversary bound of Aaronson. For partial functions, we show unbounded separations between $\text{fbs}(f)$ and other adversary bounds, as well as between the relational and Kolmogorov complexity bounds.
We also show that, for partial functions, fractional block sensitivity cannot give lower bounds larger than $\sqrt{n \cdot \text{bs}(f)}$, where $n$ is the number of variables and $\text{bs}(f)$ is the block sensitivity. Then we exhibit a partial function $f$ that matches this upper bound, $\text{fbs}(f) = \Omega(\sqrt{n \cdot \text{bs}(f)})$.Sun, 08 Oct 2017 08:06:26 +0300https://eccc.weizmann.ac.il/report/2017/150TR17-149 | Prediction from Partial Information and Hindsight, with Application to Circuit Lower Bounds |
Or Meir,
Avi Wigderson
https://eccc.weizmann.ac.il/report/2017/149Consider a random sequence of $n$ bits that has entropy at least $n-k$, where $k\ll n$. A commonly used observation is that an average coordinate of this random sequence is close to being uniformly distributed, that is, the coordinate “looks random”. In this work, we prove a stronger result that says, roughly, that the average coordinate looks random to an adversary that is allowed to query $\approx\frac{n}{k}$ other coordinates of the sequence, even if the adversary is non-deterministic. This setting generalizes decision trees and certificates for Boolean functions.
As an application of this result, we prove a new result on depth-$3$ circuits, which recovers as a direct corollary the known lower bounds for the parity and majority functions, as well as a lower bound on sensitive functions due to Boppana (IPL 63(5), 1997). An interesting feature of this proof is that it works in the framework of Karchmer and Wigderson (SIDMA 3(2), 1990), and in particular it is a “top-down” proof (Hastad, Jukna and Pudlak, Computational Complexity 5(2), 1995). Finally, it yields a new kind of a random restriction lemma for non-product distributions, which may be of independent interest. Sun, 08 Oct 2017 07:51:58 +0300https://eccc.weizmann.ac.il/report/2017/149