ECCC - Reportshttps://eccc.weizmann.ac.il/Latest Reports published at https://eccc.weizmann.ac.ilen-usTue, 14 Jul 2020 16:43:02 +0300TR20-105 | Automating Regular or Ordered Resolution is NP-Hard |
Zoë Bell
https://eccc.weizmann.ac.il/report/2020/105We show that is hard to find regular or even ordered (also known as Davis-Putnam) Resolution proofs, extending the breakthrough result for general Resolution from Atserias and Müller to these restricted forms. Namely, regular and ordered Resolution are automatable if and only if P = NP. Specifically, for a CNF formula $F$ the problem of distinguishing between the existence of a polynomial-size ordered Resolution refutation of $F$ and an at least exponential-size general Resolution proof being required to refute $F$ is NP-complete.Tue, 14 Jul 2020 16:43:02 +0300https://eccc.weizmann.ac.il/report/2020/105TR20-104 | On Counting $t$-Cliques Mod 2 |
Oded Goldreich
https://eccc.weizmann.ac.il/report/2020/104For a constant integer $t$, we consider the problem of counting the number of $t$-cliques $\bmod 2$ in a given graph.
We show that this problem is not easier than determining whether a given graph contains a $t$-clique, and present a simple worst-case to average-case reduction for it. The reduction runs in linear time when graphs are presented by their adjacency matrices, and average-case is with respect to the uniform distribution over graphs with a given number of vertices.
Sun, 12 Jul 2020 18:14:08 +0300https://eccc.weizmann.ac.il/report/2020/104TR20-103 | One-Tape Turing Machine and Branching Program Lower Bounds for MCSP |
Mahdi Cheraghchi,
Shuichi Hirahara,
Dimitrios Myrisiotis,
Yuichi Yoshida
https://eccc.weizmann.ac.il/report/2020/103 For a size parameter $s\colon\mathbb{N}\to\mathbb{N}$, the Minimum Circuit Size Problem (denoted by ${\rm MCSP}[s(n)]$) is the problem of deciding whether the minimum circuit size of a given function $f \colon \{0,1\}^n \to \{0,1\}$ (represented by a string of length $N := 2^n$) is at most a threshold $s(n)$. A recent line of work exhibited ``hardness magnification'' phenomena for MCSP: A very weak lower bound for MCSP implies a breakthrough result in complexity theory. For example, McKay, Murray, and Williams (STOC 2019) implicitly showed that, for some constant $\mu_1 > 0$, if ${\rm MCSP}[2^{\mu_1\cdot n}]$ cannot be computed by a one-tape Turing machine (with an additional one-way read-only input tape) running in time $N^{1.01}$, then ${\rm P}\neq{\rm NP}$.
In this paper, we present the following new lower bounds against one-tape Turing machines and branching programs:
\begin{enumerate}
\item A randomized two-sided error one-tape Turing machine (with an additional one-way read-only input tape) cannot compute ${\rm MCSP}[2^{\mu_2\cdot n}]$ in time $N^{1.99}$, for some constant $\mu_2 > \mu_1$.
\item A non-deterministic (or parity) branching program of size $o(N^{1.5}/\log N)$ cannot compute MKTP, which is a time-bounded Kolmogorov complexity analogue of MCSP. This is shown by directly applying the Nechiporuk method to MKTP, which previously appeared to be difficult.
\end{enumerate}
These results are the first non-trivial lower bounds for MCSP and MKTP against one-tape Turing machines and non-deterministic branching programs, and essentially match the best-known lower bounds for any explicit functions against these computational models.
The first result is based on recent constructions of pseudorandom generators for read-once oblivious branching programs (ROBPs) and combinatorial rectangles (Forbes and Kelley, FOCS 2018; Viola 2019). En route, we obtain several related results:
\begin{enumerate}
\item There exists a (local) hitting set generator with seed length $\widetilde{O}(\sqrt{N})$ secure against read-once polynomial-size non-deterministic branching programs on $N$-bit inputs.
\item Any read-once co-non-deterministic branching program computing MCSP must have size at least $2^{\widetilde{\Omega}(N)}$.
\end{enumerate}Sat, 11 Jul 2020 08:31:21 +0300https://eccc.weizmann.ac.il/report/2020/103TR20-102 | Notes on Hazard-Free Circuits |
Stasys Jukna
https://eccc.weizmann.ac.il/report/2020/102The problem of constructing hazard-free Boolean circuits (those avoiding electronic glitches) dates back to the 1940s and is an important problem in circuit design. Recently, Ikenmeyer et al. [J. ACM, 66:4 (2019), Article 25] have shown that the hazard-free circuit complexity of any Boolean function $f(x)$ is lower-bounded by the monotone circuit complexity of the monotone Boolean function which accepts an input $x$ iff $f(z)=1$ for some vector $z\leq x$. We give a short and amazingly simple proof of this interesting result. We also show that a circuit is hazard-free if and only if the circuit and its dual produce (purely syntactically) all prime implicants of the functions they compute. This extends a classical result of Eichelberger [IBM J. Res. Develop., 9 (1965)] showing this property for depth-two circuits producing no terms containing a variable together with its negation. Finally, we give a very simple non-monotone Boolean function whose hazard-free circuit complexity is super-polynomially larger than its unrestricted circuit complexity.Thu, 09 Jul 2020 22:01:07 +0300https://eccc.weizmann.ac.il/report/2020/102TR20-101 | Lower Bounds for XOR of Forrelations |
Uma Girish,
Ran Raz,
Wei Zhan
https://eccc.weizmann.ac.il/report/2020/101The Forrelation problem, first introduced by Aaronson [AA10] and Aaronson and Ambainis [AA15], is a well studied computational problem in the context of separating quantum and classical computational models. Variants of this problem were used to give tight separations between quantum and classical query complexity [AA15]; the first separation between poly-logarithmic quantum query complexity and bounded-depth circuits of super-polynomial size, a result that also implied an oracle separation of the classes BQP and PH [RT19]; and improved separations between quantum and classical communication complexity [GRT19]. In all these separations, the lower bound for the classical model only holds when the advantage of the protocol (over a random guess) is more than $\approx 1/\sqrt{N}$, that is, the success probability is larger than $\approx 1/2 + 1/\sqrt{N}$. This is unavoidable as $\approx 1/\sqrt{N}$ is the correlation between two coordinates of an input that is sampled from the Forrelation distribution, and hence there are simple classical protocols that achieve advantage $\approx 1/\sqrt{N}$, in all these models.
To achieve separations when the classical protocol has smaller advantage, we study in this work the XOR of $k$ independent copies of (a variant of) the Forrelation function (where $k\ll N$). We prove a very general result that shows that any family of Boolean functions that is closed under restrictions, whose Fourier mass at level $2k$ is bounded by $\alpha^k$ (that is, the sum of the absolute values of all Fourier coefficients at level $2k$ is bounded by $\alpha^k$), cannot compute the XOR of $k$ independent copies of the Forrelation function with advantage better than $O\left(\frac{\alpha^k}{{N^{k/2}}}\right)$. This is a strengthening of a result of [CHLT19], that gave a similar statement for $k=1$, using the technique of [RT19]. We give several applications of our result. In particular, we obtain the following separations:
Quantum versus Classical Communication Complexity: We give the first example of a partial Boolean function that can be computed by a simultaneous-message quantum protocol with communication complexity $\mbox{polylog}(N)$ (where Alice and Bob also share $\mbox{polylog}(N)$ EPR pairs), and such that, any classical randomized protocol of communication complexity at most $\tilde{o}(N^{1/4})$, with any number of rounds, has quasipolynomially small advantage over a random guess. Previously, only separations where the classical protocol has polynomially small advantage were known between these models [G16, GRT19].
Quantum Query Complexity versus Bounded Depth Circuits: We give the first example of a partial Boolean function that has a quantum query algorithm with query complexity $\mbox{polylog}(N)$, and such that, any constant-depth circuit of quasipolynomial size has quasipolynomially small advantage over a random guess. Previously, only separations where the constant-depth circuit has polynomially small advantage were known [RT19].
Tue, 07 Jul 2020 19:03:43 +0300https://eccc.weizmann.ac.il/report/2020/101TR20-100 | Streaming Verification for Graph Problems: Optimal Tradeoffs and Nonlinear Sketches |
Amit Chakrabarti,
Prantar Ghosh,
Justin Thaler
https://eccc.weizmann.ac.il/report/2020/100We study graph computations in an enhanced data streaming setting, where a space-bounded client reading the edge stream of a massive graph may delegate some of its work to a cloud service. We seek algorithms that allow the client to verify a purported proof sent by the cloud service that the work done in the cloud is correct.
A line of work starting with Chakrabarti et al. (ICALP 2009) has provided such algorithms, which we call schemes, for several statistical and graph-theoretic problems, many of which exhibit a tradeoff between the length of the proof and the space used by the streaming verifier.
This work designs new schemes for a number of basic graph problems---including triangle counting, maximum matching, topological sorting, and single-source shortest paths---where past work had either failed to obtain smooth tradeoffs between these two key complexity measures or only obtained suboptimal tradeoffs. Our key innovation is having the verifier compute certain nonlinear sketches of the input stream, leading to either new or improved tradeoffs. In many cases, our schemes in fact provide optimal tradeoffs up to logarithmic factors.
Specifically, for most graph problems that we study, it is known that the product of the verifier's space cost $v$ and the proof length $h$ must be at least $\Omega(n^2)$ for $n$-vertex graphs. However, matching upper bounds are only known for a handful of settings of $h$ and $v$ on the curve $h \cdot v=\tilde{\Theta}(n^2)$. For example, for counting triangles and maximum matching, schemes with costs lying on this curve are only known for $(h=\tilde{O}(n^2), v=\tilde{O}(1))$, $(h=\tilde{O}(n), v=\tilde{O}(n))$, and the trivial $(h=\tilde{O}(1), v=\tilde{O}(n^2))$. A major message of this work is that by exploiting nonlinear sketches, a significant ``portion'' of costs on the tradeoff curve $h \cdot v = n^2$ can be achieved.Mon, 06 Jul 2020 20:16:45 +0300https://eccc.weizmann.ac.il/report/2020/100TR20-099 | KRW Composition Theorems via Lifting |
Susanna de Rezende,
Or Meir,
Jakob Nordström,
Toniann Pitassi,
Robert Robere
https://eccc.weizmann.ac.il/report/2020/099One of the major open problems in complexity theory is proving super-logarithmic lower bounds on the depth of circuits (i.e., $\mathbf{P}\not\subseteq\mathbf{NC}^1$). Karchmer, Raz, and Wigderson (Computational Complexity 5(3/4), 1995) suggested to approach this problem by proving that depth complexity behaves “as expected” with respect to the composition of functions $f \diamond g$. They showed that the validity of this conjecture would imply that $\mathbf{P}\not\subseteq\mathbf{NC}^1$.
Several works have made progress toward resolving this conjecture by proving special cases. In particular, these works proved the KRW conjecture for every outer function $f$, but only for few inner functions $g$. Thus, it is an important challenge to prove the KRW conjecture for a wider range of inner functions.
In this work, we extend significantly the range of inner functions that can be handled. First, we consider the $\textit{monotone}$ version of the KRW conjecture. We prove it for every monotone inner function $g$ whose depth complexity can be lower bounded via a query-to-communication lifting theorem. This allows us to handle several new and well-studied functions such as the $s\textbf{-}t$-connectivity, clique, and generation functions.
In order to carry this progress back to the $\textit{non-monotone}$ setting, we introduce a new notion of $\textit{semi-monotone}$ composition, which combines the non-monotone complexity of the outer function $f$ with the monotone complexity of the inner function $g$. In this setting, we prove the KRW conjecture for a similar selection of inner functions $g$, but only for a specific choice of the outer function $f$.Mon, 06 Jul 2020 14:22:16 +0300https://eccc.weizmann.ac.il/report/2020/099TR20-098 | Impossibility of Derandomizing the Isolation Lemma for all Families |
Rohit Gurjar,
Thomas Thierauf,
Manindra Agrawal
https://eccc.weizmann.ac.il/report/2020/098The Isolation Lemma states that when random weights are assigned to the elements of a finite set $E$, then in any given family of subsets of $E$, exactly one set has the minimum weight, with high probability. In this note, we present two proofs for the fact that it is impossible to efficiently derandomize the Isolation Lemma for arbitrary families.
The first proof is from Chari, Rohatgi and Srinivasan and uses the potential method. An alternate proof is due to the first author of this note. It uses the polynomial method. However, it is not written anywhere. The main purpose of this note is to present that proof. Additionally we show that the above lower bounds are almost tight with respect to various parameters.
Sun, 05 Jul 2020 09:22:25 +0300https://eccc.weizmann.ac.il/report/2020/098TR20-097 | 6-Uniform Maker-Breaker Game Is PSPACE-Complete |
Md Lutfar Rahman,
Thomas Watson
https://eccc.weizmann.ac.il/report/2020/097In a STOC 1976 paper, Schaefer proved that it is PSPACE-complete to determine the winner of the so-called Maker-Breaker game on a given set system, even when every set has size at most 11. Since then, there has been no improvement on this result. We prove that the game remains PSPACE-complete even when every set has size 6.Tue, 30 Jun 2020 18:23:11 +0300https://eccc.weizmann.ac.il/report/2020/097TR20-096 | On the asymptotic complexity of sorting |
Igor Sergeev
https://eccc.weizmann.ac.il/report/2020/096We investigate the number of pairwise comparisons sufficient to sort $n$ elements chosen from a linearly ordered set. This number is shown to be $\log_2(n!) + o(n)$ thus improving over the previously known upper bounds of the form $\log_2(n!) + \Theta(n)$. The new bound is achieved by the proposed group insertion sorting algorithm. Wed, 24 Jun 2020 20:41:11 +0300https://eccc.weizmann.ac.il/report/2020/096