ECCC - Reportshttps://example.com/Latest Reports published at https://eccc.weizmann.ac.ilen-usTue, 15 Aug 2017 20:37:03 +0300TR17-128 | The Direct Sum of Universal Relations |
Or Meir
https://eccc.weizmann.ac.il/report/2017/128The universal relation is the communication problem in which Alice and Bob get as inputs two distinct strings, and they are required to find a coordinate on which the strings differ. The study of this problem is motivated by its connection to Karchmer-Wigderson relations, which are communication problems that are tightly related to circuit-depth lower bounds.
In this paper, we prove a direct sum theorem for the universal relation, namely, we prove that solving $m$ independent instances of the universal relation is $m$ times harder than solving a single instance. More specifically, it is known that the deterministic communication complexity of the universal relation is at least $n$. We prove that the deterministic communication complexity of solving $m$ independent instances of the universal relation is at least $m \cdot (n-O(\log m))$.Tue, 15 Aug 2017 20:37:03 +0300https://eccc.weizmann.ac.il/report/2017/128TR17-127 | Isolating a Vertex via Lattices: Polytopes with Totally Unimodular Faces |
Thomas Thierauf,
Rohit Gurjar,
Nisheeth Vishnoi
https://eccc.weizmann.ac.il/report/2017/127We deterministically construct quasi-polynomial weights in quasi-polynomial time, such that in a given polytope with totally unimodular constraints, one vertex is isolated, i.e., there is a unique minimum weight vertex.
More precisely,
the property that we need is that every face of the polytope lies in an affine space defined by a totally unimodular matrix.
This derandomizes the famous Isolation Lemma by Mulmuley, Vazirani, and Vazirani for this setting, generalizes the recent derandomization results for bipartite perfect matching and matroid intersection, and resolves the problem of derandomizing the isolation lemma for polytopes with totally unimodular constraints.
We prove our result by associating a lattice to each face of the polytope and showing that if there is a totally unimodular kernel matrix for this lattice, then the number of near-shortest vectors in it is polynomially bounded.
The proof of this latter geometric fact is combinatorial and follows from a polynomial bound on the number of near-shortest circuits in a regular matroid. This is the technical core of the paper and relies on Seymour's decomposition theorem for regular matroids. It generalizes an influential result by Karger on the number of minimum cuts in a graph to regular matroids. Both of our results, on lattices and matroids, should be of independent interest.Sat, 12 Aug 2017 14:14:41 +0300https://eccc.weizmann.ac.il/report/2017/127TR17-126 | Local Testing and Decoding of High-Rate Error-Correcting Codes |
Swastik Kopparty,
Shubhangi Saraf
https://eccc.weizmann.ac.il/report/2017/126We survey the state of the art in constructions of locally testable
codes, locally decodable codes and locally correctable codes of high rate.
Mon, 07 Aug 2017 22:27:14 +0300https://eccc.weizmann.ac.il/report/2017/126TR17-125 | Dimension Reduction for Polynomials over Gaussian Space and Applications |
Badih Ghazi,
Pritish Kamath,
Prasad Raghavendra
https://eccc.weizmann.ac.il/report/2017/125In this work we introduce a new technique for reducing the dimension of the ambient space of low-degree polynomials in the Gaussian space while preserving their relative correlation structure. As applications, we address the following problems:
(I) Computability of the Approximately Optimal Noise Stable function over Gaussian space:
The goal here is to find a partition of $\mathbb{R}^n$ into $k$ parts, that maximizes the noise stability. An $\varepsilon$-optimal partition is one which is within additive $\varepsilon$ of the optimal noise stability.
De, Mossel & Neeman (CCC 2017) raised the question of an explicit (computable) bound on the dimension $n_0(\varepsilon)$ in which we can find an $\varepsilon$-optimal partition.
De et al. already provide such an explicit bound. Using our dimension reduction technique, we are able to obtain improved explicit bounds on the dimension $n_0(\varepsilon)$.
(II) Decidability of Approximate Non-Interactive Simulation of Joint Distributions:
A "non-interactive simulation" problem is specified by two distributions $P(x,y)$ and $Q(u,v)$: The goal is to determine if two players, Alice and Bob, that observe sequences $X^n$ and $Y^n$ respectively where $\{(X_i, Y_i)\}_{i=1}^n$ are drawn i.i.d. from $P(x,y)$ can generate pairs $U$ and $V$ respectively (without communicating with each other) with a joint distribution that is arbitrarily close in total variation to $Q(u,v)$. Even when $P$ and $Q$ are extremely simple, it is open in several cases if $P$ can simulate $Q$.
Ghazi, Kamath & Sudan (FOCS 2016) formulated a gap problem of deciding whether there exists a non-interactive simulation protocol that comes $\varepsilon$-close to simulating $Q$, or does every non-interactive simulation protocol remain $2\varepsilon$-far from simulating $Q$? The main underlying challenge here is to determine an explicit (computable) upper bound on the number of samples $n_0(\varepsilon)$ that can be drawn from $P(x,y)$ to get $\varepsilon$-close to $Q$ (if it were possible at all).
While Ghazi et al. answered the challenge in the special case where $Q$ is a joint distribution over $\{0,1\} \times \{0,1\}$, it remained open to answer the case where $Q$ is a distribution over larger alphabet, say $[k] \times [k]$ for $k > 2$. Recently De, Mossel & Neeman (in a follow-up work), address this challenge for all $k \ge 2$. In this work, we are able to recover this result as well, with improved explicit bounds on $n_0(\varepsilon)$.
---
Our technique of dimension reduction for low-degree polynomials is simple and analogous to the Johnson-Lindenstrauss lemma, and could be of independent interest.Mon, 07 Aug 2017 21:50:15 +0300https://eccc.weizmann.ac.il/report/2017/125TR17-124 | An Almost Quadratic Lower Bound for Syntactically Multilinear Arithmetic Circuits |
Mrinal Kumar,
Ben Lee Volk
https://eccc.weizmann.ac.il/report/2017/124We prove a lower bound of $\Omega(n^2/\log^2 n)$ on the size of any syntactically multilinear arithmetic circuit computing some explicit multilinear polynomial $f(x_1, \ldots, x_n)$. Our approach expands and improves upon a result of Raz, Shpilka and Yehudayoff [RSY08], who proved a lower bound of $\Omega(n^{4/3}/\log^2 n)$ for the same polynomial. Our improvement follows from an asymptotically optimal lower bound, in a certain range of parameters, for a generalized version of Galvin's problem in extremal set theory.
Mon, 07 Aug 2017 09:23:26 +0300https://eccc.weizmann.ac.il/report/2017/124TR17-123 | Quadratically Tight Relations for Randomized Query Complexity |
Dmitry Gavinsky,
Rahul Jain,
Hartmut Klauck,
Srijita Kundu,
Troy Lee,
Miklos Santha,
Swagato Sanyal,
Jevgenijs Vihrovs
https://eccc.weizmann.ac.il/report/2017/123Let $f:\{0,1\}^n \rightarrow \{0,1\}$ be a Boolean function. The certificate complexity $C(f)$ is a complexity measure that is quadratically tight for the zero-error randomized query complexity $R_0(f)$: $C(f) \leq R_0(f) \leq C(f)^2$. In this paper we study a new complexity measure that we call expectational certificate complexity $EC(f)$, which is also a quadratically tight bound on $R_0(f)$: $EC(f) \leq R_0(f) = O(EC(f)^2)$. We prove that $EC(f) \leq C(f) \leq EC(f)^2$ and show that there is a quadratic separation between the two, thus $EC(f)$ gives a tighter upper bound for $R_0(f)$. The measure is also related to the fractional certificate complexity $FC(f)$ as follows: $FC(f) \leq EC(f) = O(FC(f)^{3/2})$. This also connects to an open question by Aaronson whether $FC(f)$ is a quadratically tight bound for $R_0(f)$, as $EC(f)$ is in fact a relaxation of $FC(f)$.
In the second part of the work, we upper bound the distributed query complexity $D^\mu_\epsilon(f)$ for product distributions $\mu$ by the square of the query corruption bound ($corr_\epsilon(f)$) which improves upon a result of Harsha, Jain and Radhakrishnan [2015]. A similar statement for communication complexity is open. Sun, 06 Aug 2017 15:06:02 +0300https://eccc.weizmann.ac.il/report/2017/123TR17-122 | Pseudorandom Bits for Oblivious Branching Programs |
Rohit Gurjar,
Ben Lee Volk
https://eccc.weizmann.ac.il/report/2017/122We construct a pseudorandom generator which fools read-$k$ oblivious branching programs and, more generally, any linear length oblivious branching program, assuming that the sequence according to which the bits are read is known in advance. For polynomial width branching programs, the seed lengths in our constructions are $\tilde{O}(n^{1-1/2^{k-1}})$ (for the read-$k$ case) and $O(n/ \log \log n)$ (for the linear length case). Previously, the best construction for these models required seed length $(1-\Omega(1))n$.Mon, 31 Jul 2017 10:16:17 +0300https://eccc.weizmann.ac.il/report/2017/122TR17-121 | Extractor-Based Time-Space Lower Bounds for Learning |
Sumegha Garg,
Ran Raz,
Avishay Tal
https://eccc.weizmann.ac.il/report/2017/121A matrix $M: A \times X \rightarrow \{-1,1\}$ corresponds to the following learning problem: An unknown element $x \in X$ is chosen uniformly at random. A learner tries to learn $x$ from a stream of samples, $(a_1, b_1), (a_2, b_2) \ldots$, where for every $i$, $a_i \in A$ is chosen uniformly at random and $b_i = M(a_i,x)$.
Assume that $k,\ell, r$ are such that any submatrix of $M$ of at least $2^{-k} \cdot |A|$ rows and at least $2^{-\ell} \cdot |X|$ columns, has a bias of at most $2^{-r}$. We show that any learning algorithm for the learning problem corresponding to $M$ requires either a memory of size at least $\Omega\left(k \cdot \ell
\right)$, or at least $2^{\Omega(r)}$ samples. The result holds even if the learner has an exponentially small success probability (of $2^{-\Omega(r)}$).
In particular, this shows that for a large class of learning problems, any learning algorithm requires either a memory of size at least $\Omega\left((\log |X|) \cdot (\log |A|)\right)$ or an exponential number of samples, achieving a tight $\Omega\left((\log |X|) \cdot (\log |A|)\right)$ lower bound on the size of the memory, rather than a bound of $\Omega\left(\min\left\{(\log |X|)^2,(\log |A|)^2\right\}\right)$ obtained in previous works [R17,MM17b].
Moreover, our result implies all previous memory-samples lower bounds, as well as a number of new applications.
Our proof builds on [R17] that gave a general technique for proving memory-samples lower bounds.Mon, 31 Jul 2017 04:14:21 +0300https://eccc.weizmann.ac.il/report/2017/121TR17-120 | Time-Space Tradeoffs for Learning from Small Test Spaces: Learning Low Degree Polynomial Functions |
Paul Beame,
Shayan Oveis Gharan,
Xin Yang
https://eccc.weizmann.ac.il/report/2017/120We develop an extension of recently developed methods for obtaining time-space tradeoff lower bounds for problems of learning from random test samples to handle the situation where the space of tests is signficantly smaller than the space of inputs, a class of learning problems that is not handled by prior work. This extension is based on a measure of how matrices amplify the 2-norms of probability distributions that is more refined than the 2-norms of these matrices.
As applications that follow from our new technique, we show that any algorithm that learns $m$-variate homogeneous polynomial functions of degree at most $d$ over $F_2$ from evaluations on randomly chosen inputs either requires space $\Omega(mn)$ or $2^{\Omega(m)}$ time where $n=m^{\Theta(d)}$ is the dimension of the space of such functions. These bounds are asymptotically optimal since they match the tradeoffs achieved by natural learning algorithms for the problems.
Mon, 31 Jul 2017 04:13:26 +0300https://eccc.weizmann.ac.il/report/2017/120TR17-119 | Resource-Efficient Common Randomness and Secret-Key Schemes |
Badih Ghazi,
T.S. Jayram
https://eccc.weizmann.ac.il/report/2017/119We study common randomness where two parties have access to i.i.d. samples from a known random source, and wish to generate a shared random key using limited (or no) communication with the largest possible probability of agreement. This problem is at the core of secret key generation in cryptography, with connections to communication under uncertainty and locality sensitive hashing. We take the approach of treating correlated sources as a critical resource, and ask whether common randomness can be generated resource-efficiently.
We consider two notable sources in this setup arising from correlated bits and correlated Gaussians. We design the first explicit schemes that use only a polynomial number of samples (in the key length) so that the players can generate shared keys that agree with constant probability using optimal communication. The best previously known schemes were both non-constructive and used an exponential number of samples. In the amortized setting, we characterize the largest achievable ratio of key length to communication in terms of the external and internal information costs, two well-studied quantities in theoretical computer science. In the relaxed setting where the two parties merely wish to improve the correlation between the generated keys of length $k$, we show that there are no interactive protocols using $o(k)$ bits of communication having agreement probability even as small as $2^{-o(k)}$. For the related communication problem where the players wish to compute a joint function $f$ of their inputs using i.i.d samples from a known source, we give a zero-communication protocol using $2^{O(c)}$ bits where $c$ is the interactive randomized public-coin communication complexity of $f$. This matches the lower bound shown previously while the best previously known upper bound was doubly exponential in $c$.Sun, 30 Jul 2017 22:00:26 +0300https://eccc.weizmann.ac.il/report/2017/119