ECCC - Reportshttps://eccc.weizmann.ac.il/Latest Reports published at https://eccc.weizmann.ac.ilen-usMon, 26 Oct 2020 23:00:01 +0200TR20-158 | A Note on Hardness under Projections for Graph Isomorphism and Time-Bounded Kolmogorov Complexity |
Eric Allender,
Azucena Garvia Bosshard,
Amulya Musipatla
https://eccc.weizmann.ac.il/report/2020/158This paper focuses on a variant of the circuit minimization problem (MCSP), denoted MKTP, which studies resource-bounded Kolmogorov complexity in place of circuit size. MCSP is not known to be hard for any complexity class under any kind of m-reducibility, but recently MKTP was shown to be hard for DET under m-reductions computable in NC0, by presenting an AC0 reduction from the rigid graph isomorphism problem to MKTP, and combining that with a theorem of Toran, showing that DET AC0-reduces to the rigid graph isomorphism problem, and then appealing to the "Gap Theorem" of [Agrawal, Allender, Rudich]. Here, we show that these reductions can be accomplished by means of projections. Thus MKTP is hard for DET under projections, and the rigid graph isomorphism problem is hard for DET under uniform projections.Mon, 26 Oct 2020 23:00:01 +0200https://eccc.weizmann.ac.il/report/2020/158TR20-157 | Batch Verification and Proofs of Proximity with Polylog Overhead |
Guy Rothblum,
Ron Rothblum
https://eccc.weizmann.ac.il/report/2020/157Suppose Alice wants to convince Bob of the correctness of k NP statements. Alice could send k witnesses to Bob, but as k grows the communication becomes prohibitive. Is it possible to convince Bob using smaller communication (without making cryptographic assumptions or bounding the computational power of a malicious Alice)? This is the question of batch verification for NP statements.
Our main result is a new interactive proof protocol for verifying the correctness of k UP statements (NP statements with a unique witness) using communication that is poly-logarithmic in k (and a fixed polynomial in the length of a single witness).
This result is obtained by making progress on a different question in the study of interactive proofs. Suppose Alice wants to convince Bob that a huge dataset has some property. Can this be done if Bob can't even read the entire input? In other words, what properties can be verified in sublinear time? An Interactive Proof of Proximity guarantees that Bob accepts if the input has the property, and rejects if the input is far (say in Hamming distance) from having the property. Two central complexity measures of such a protocol are the query and communication complexities (which should both be sublinear). For every query parameter $q$, and for every language in logspace uniform NC, we construct an interactive proof of proximity with query complexity $q$ and communication complexity $(n/q) \cdot \polylog(n)$.
Both results are optimal up to poly-logarithmic factors, under reasonable complexity-theoretic or cryptographic assumptions. The second result, which is our main technical contribution, builds on a distance amplification technique introduced in a beautiful recent work of Ben-Sasson, Kopparty and Saraf [CCC 2018].Sun, 25 Oct 2020 12:51:48 +0200https://eccc.weizmann.ac.il/report/2020/157TR20-156 | Codes over integers, and the singularity of random matrices with large entries |
Sankeerth Rao Karingula,
Shachar Lovett
https://eccc.weizmann.ac.il/report/2020/156The prototypical construction of error correcting codes is based on linear codes over finite fields. In this work, we make first steps in the study of codes defined over integers. We focus on Maximum Distance Separable (MDS) codes, and show that MDS codes with linear rate and distance can be realized over the integers with a constant alphabet size. This is in contrast to the situation over finite fields, where a linear size finite field is needed.
The core of this paper is a new result on the singularity probability of random matrices. We show that for a random $n \times n$ matrix with entries chosen independently from the range $\{-m,\ldots,m\}$, the probability that it is singular is at most $m^{-cn}$ for some absolute constant $c>0$.Thu, 22 Oct 2020 08:36:16 +0300https://eccc.weizmann.ac.il/report/2020/156TR20-155 | Log-rank and lifting for AND-functions |
Sam McGuire,
Shachar Lovett,
Alexander Knop,
Weiqiang Yuan
https://eccc.weizmann.ac.il/report/2020/155Let $f: \{0,1\}^n \to \{0, 1\}$ be a boolean function, and let $f_\land (x, y) = f(x \land y)$ denote the AND-function of $f$, where $x \land y$ denotes bit-wise AND. We study the deterministic communication complexity of $f_\land$ and show that, up to a $\log n$ factor, it is bounded by a polynomial in the logarithm of the real rank of the communication matrix of $f_\land$. This comes within a $\log n$ factor of establishing the log-rank conjecture for AND-functions with no assumptions on $f$. Our result stands in contrast with previous results on special cases of the log-rank
conjecture, which needed significant restrictions on $f$ such as monotonicity or low $\mathbb{F}_2$-degree. Our techniques can also be used to prove (within a $\log n$ factor) a lifting theorem for AND-functions, stating that the deterministic communication complexity of $f_\land$ is polynomially-related to the AND-decision tree complexity of $f$.
The results rely on a new structural result regarding boolean functions $f:\{0, 1\}^n \to \{0, 1\}$ with a sparse polynomial representation, which may be of independent interest. We show that if the polynomial computing $f$ has few monomials then the set system of the monomials has a small hitting set, of size poly-logarithmic in its sparsity. We also establish extensions of this result to multi-linear polynomials $f:\{0,1\}^n \to \mathbb{R}$ with a larger range.
Sun, 18 Oct 2020 17:44:03 +0300https://eccc.weizmann.ac.il/report/2020/155TR20-154 | A Structural Theorem for Local Algorithms with Applications to Coding, Testing, and Privacy |
Marcel Dall'Agnol,
Tom Gur,
Oded Lachish
https://eccc.weizmann.ac.il/report/2020/154We prove a general structural theorem for a wide family of local algorithms, which includes property testers, local decoders, and PCPs of proximity. Namely, we show that the structure of every algorithm that makes $q$ adaptive queries and satisfies a natural robustness condition admits a sample-based algorithm with $n^{1- 1/O(q^2 \log^2 q)}$ sample complexity, following the definition of Goldreich and Ron (TOCT 2016). We prove that this transformation is nearly optimal. Our theorem also admits a scheme for constructing privacy-preserving local algorithms.
Using the unified view that our structural theorem provides, we obtain results regarding various types of local algorithms, including the following.
- We strengthen the state-of-the-art lower bound for relaxed locally decodable codes, obtaining an exponential improvement on the dependency in query complexity; this resolves an open problem raised by Gur and Lachish (SODA 2020).
- We show that any (constant-query) testable property admits a sample-based tester with sublinear sample complexity; this resolves a problem left open in a work of Fischer, Lachish, and Vasudev (FOCS 2015) by extending their main result to adaptive testers.
- We prove that the known separation between proofs of proximity and testers is essentially maximal; this resolves a problem left open by Gur and Rothblum (ECCC 2013, Computational Complexity 2018) regarding sublinear-time delegation of computation.
Our techniques strongly rely on relaxed sunflower lemmas and the Hajnal–Szemerédi theorem.Sat, 10 Oct 2020 14:21:31 +0300https://eccc.weizmann.ac.il/report/2020/154TR20-153 | Total Functions in the Polynomial Hierarchy |
Robert Kleinberg,
Daniel Mitropolsky,
Christos Papadimitriou
https://eccc.weizmann.ac.il/report/2020/153We identify several genres of search problems beyond NP for which existence of solutions is guaranteed. One class that seems especially rich in such problems is PEPP (for "polynomial empty pigeonhole principle"), which includes problems related to existence theorems proved through the union bound, such as finding a bit string that is far from all codewords, finding an explicit rigid matrix, as well as a problem we call Complexity, capturing Complexity Theory's quest. When the union bound is generous, in that solutions constitute at least a polynomial fraction of the domain, we have a family of seemingly weaker classes $\alpha$-PEPP, which are inside FP}$^{\text{NP}}|$poly. Higher in the hierarchy, we identify the constructive version of the Sauer-Shelah lemma and the appropriate generalization of PPP that contains it. The resulting total function hierarchy turns out to be more stable than the polynomial hierarchy: it is known that, under oracles, total functions within FNP may be easy, but total functions a level higher may still be harder than FP$^{\text{NP}}$.Fri, 09 Oct 2020 01:31:10 +0300https://eccc.weizmann.ac.il/report/2020/153TR20-152 | Variants of the Determinant polynomial and VP-completeness |
Prasad Chaugule,
Nutan Limaye,
Shourya Pandey
https://eccc.weizmann.ac.il/report/2020/152The determinant is a canonical VBP-complete polynomial in the algebraic complexity setting. In this work, we introduce two variants of the determinant polynomial which we call $StackDet_n(X)$ and $CountDet_n(X)$ and show that they are VP and VNP complete respectively under $p$-projections. The definitions of the polynomials are inspired by a combinatorial characterisation of the determinant developed by Mahajan and Vinay (SODA 1997). We extend the combinatorial object in their work, namely clow sequences, by introducing additional edge labels on the edges of the underlying graph. The idea of using edge labels is inspired by the work of Mengel (MFCS 2013). Fri, 09 Oct 2020 01:27:25 +0300https://eccc.weizmann.ac.il/report/2020/152TR20-151 | Pseudobinomiality of the Sticky Random Walk |
Venkatesan Guruswami,
Vinayak Kumar
https://eccc.weizmann.ac.il/report/2020/151Random walks on expanders are a central and versatile tool in pseudorandomness. If an arbitrary half of the vertices of an expander graph are marked, known Chernoff bounds for expander walks imply that the number $M$ of marked vertices visited in a long $n$-step random walk strongly concentrates around the expected $n/2$ value. Surprisingly, it was recently shown that the parity of $M$ also has exponentially small bias.
Is there a common unification of these results? What other statistics about $M$ resemble the binomial distribution (the Hamming weight of a random $n$-bit string)? To gain insight into such questions, we analyze a simpler model called the sticky random walk. This model is a natural stepping stone towards understanding expander random walks, and we also show that it is a necessary step. The sticky random walk starts with a random bit and then each subsequent bit independently equals the previous bit with probability $(1+\lambda)/2$. Here $\lambda$ is the proxy for the expander's (second largest) eigenvalue.
Using Krawtchouk expansion of functions, we derive several probabilistic results about the sticky random walk. We show an asymptotically tight $\Theta(\lambda)$ bound on the total variation distance between the (Hamming weight of the) sticky walk and the binomial distribution. We prove that the correlation between the majority and parity bit of the sticky walk is bounded by $O(n^{-1/4})$. This lends hope to unifying Chernoff bounds and parity concentration, as well as establishing other interesting statistical properties, of expander random walks.
Thu, 08 Oct 2020 17:03:25 +0300https://eccc.weizmann.ac.il/report/2020/151TR20-150 | Almost-Everywhere Circuit Lower Bounds from Non-Trivial Derandomization |
Lijie Chen,
Xin Lyu,
Ryan Williams
https://eccc.weizmann.ac.il/report/2020/150In certain complexity-theoretic settings, it is notoriously difficult to prove complexity separations which hold almost everywhere, i.e., for all but finitely many input lengths. For example, a classical open question is whether $\mathrm{NEXP} \subset \mathrm{i.o.-}\mathrm{NP}$; that is, it is open whether nondeterministic exponential time computations can be simulated on infinitely many input lengths by $\mathrm{NP}$ algorithms. This difficulty also applies to Williams' algorithmic method for circuit lower bounds [Williams, J. ACM 2014]. In particular, although [Murray and Williams, STOC 2018] proved $\mathrm{NTIME}[2^{\mathrm{polylog}(n)}] \not\subset \mathrm{ACC}^0$, it has remained an open problem to show that $\mathrm{E}^{\mathrm{NP}}$ ($2^{O(n)}$ time with an $\mathrm{NP}$ oracle) is not contained in $\mathrm{i.o.-}\mathrm{ACC}^0$.
In this paper, we show how many infinitely-often circuit lower bounds proved by the algorithmic method can be adapted to establish almost-everywhere lower bounds.
- We show there is a function $f \in \mathrm{E}^{\mathrm{NP}}$ such that for all sufficiently large input lengths $n$ and $\varepsilon \leq o(1)$, $f$ cannot be $(1/2+2^{-n^{\varepsilon}})$-approximated by $2^{n^\varepsilon}$-size $\mathrm{ACC}^0$ circuits on inputs of length $n$, improving lower bounds in [Chen and Ren, STOC 2020] and [Viola, ECCC 2020].
- We construct rigid matrices in $\mathrm{P}^{\mathrm{NP}}$ for all but finitely many inputs, rather than infinitely often as in [Alman and Chen, FOCS 2019] and [Bhangale et al., FOCS 2020].
- We show there are functions in $\mathrm{E}^{\mathrm{NP}}$ requiring constant-error probabilistic degree at least $\Omega(n/\log^2 n)$ for all large enough $n$, improving an infinitely-often separation of [Viola, ECCC 2020].
Our key to proving almost-everywhere worst-case lower bounds is a new ``constructive'' proof of an NTIME hierarchy theorem proved by [Fortnow and Santhanam, CCC 2016], where we show for every ``weak'' nondeterminstic algorithm (with smaller running-time and short witness), a ``refuter algorithm'' exists that can construct ``bad'' inputs for the hard language. We use this refuter algorithm to construct an almost-everywhere hard function. To extend our lower bounds to the average case, we prove a new XOR Lemma based on approximate linear sums, and combine it with the PCP-of-proximity applications developed in [Chen and Williams, CCC 2019] and [Chen and Ren, STOC 2020]. As a byproduct of our new XOR Lemma, we obtain a nondeterministic pseudorandom generator for poly-size $\mathrm{ACC}^0$ circuits with seed length $\mathrm{polylog}(n)$, which resolves an open question in [Chen and Ren, STOC 2020].Thu, 08 Oct 2020 16:53:53 +0300https://eccc.weizmann.ac.il/report/2020/150TR20-149 | Robustly Self-Ordered Graphs: Constructions and Applications to Property Testing |
Oded Goldreich,
Avi Wigderson
https://eccc.weizmann.ac.il/report/2020/149
A graph $G$ is called {\em self-ordered}\/ (a.k.a asymmetric) if the identity permutation is its only automorphism.
Equivalently, there is a unique isomorphism from $G$ to any graph that is isomorphic to $G$.
We say that $G=(V,E)$ is {\em robustly self-ordered}\/ if the size of the symmetric difference between $E$ and the edge-set of the graph obtained by permuting $V$ using any permutation $\pi:V\to V$ is proportional to the number of non-fixed-points of $\pi$.
We show that robustly self-ordered bounded-degree graphs exist (in abundance), and that they can be constructed efficiently, in a strong sense.
Specifically, given the index of a vertex in such a graph, it is possible to find all its neighbors in polynomial-time (i.e., in time that is poly-logarithmic in the size of the graph).
We provide two very different constructions, in tools and structure.
The first, a direct construction, is based on proving a sufficient condition for robust self-ordering,
which requires that an auxiliary graph, on {\em pairs|}\/ of vertices of the original graph, is expanding.
In this case the original graph is (not only robustly self-ordered but) also expanding.
The second construction proceeds in three steps: It boosts the mere existence of robustly self-ordered graphs,
which provides explicit graphs of sublogarithmic size, to an efficient construction of polynomial-size graphs,
and then, repeating it again, to exponential-size(robustly self-ordered) graphs that are locally constructible.
This construction can yield robustly self-ordered graphs that are either expanders or highly disconnected, having logarithmic size connected components.
We also consider graphs of unbounded degree, seeking correspondingly unbounded robustness parameters.
We again demonstrate that such graphs (of linear degree) exist (in abundance), and give an explicit construction.
This turns out to require very different tools, and the definition and constructions of new pseudo-random objects.
Specifically, we show that the construction of such graphs reduces to the construction of non-malleable two-source extractors
with very weak parameters but with an additional natural feature.
Next, we reduce the construction of such non-malleable two-source extractors to the construction of ``relocation-detecting'' codes. Loosely speaking, in such code permuting arbitrarily the coordinates of a random codeword yields a string that is far any other codeword. We conclude by showing how to construct relocation-detecting codes (of various types, including ones with constant rate).
We demonstrate that robustly self-ordered bounded-degree graphs are useful towards obtaining lower bounds on the query complexity of testing graph properties both in the bounded-degree and the dense graph models.
Indeed, their robustness offers efficient, local and distance preserving reductions from testing problems on ordered structures (like sequences) to the unordered (effectively unlabeled) graphs.
One of the results that we obtain, via such a reduction, is a subexponential separation
between the complexity of testing and tolerant testing of graph properties in the bounded-degree graph model.
Tue, 29 Sep 2020 22:33:10 +0300https://eccc.weizmann.ac.il/report/2020/149