Zeev Dvir

FOCS Conference 2022 Conference Paper

Linear Hashing with ℓ∞ guarantees and two-sided Kakeya bounds

• Manik Dhar
• Zeev Dvir

We show that a randomly chosen linear map over a finite field gives a good hash function in the $\ell_{\infty}$ sense. More concretely, consider a set $S\subset\mathbb{F}_{q}^{n}$ and a randomly chosen linear ${map}L: \mathbb{F}_{q}^{n}\rightarrow\mathbb{F}_{q}^{t}$ with q t taken to be sufficiently smaller than $|S|$. Let U S denote a random variable distributed uniformly on S. Our main theorem shows that, with high probability over the choice of L, the random variable $L(U_{S})$ is close to uniform in the $\ell_{\infty}$ norm. In other words, every element in the range $\mathbb{F}_{q}^{t}$ has about the same number of elements in S mapped to it. This complements the widely-used Leftover Hash Lemma (LHL) which proves the analog statement under the statistical, or $\ell_{1}$, distance (for a richer class of functions) as well as prior work on the expected largest ’bucket size’ in linear hash functions [1]. By known bounds from the load balancing literature [2], our results are tight and show that linear functions hash as well as truly random function up to a constant factor in the entropy loss. Our proof leverages a connection between linear hashing and the finite field Kakeya problem and extends some of the tools developed in this area, in particular the polynomial method.

STOC Conference 2019 Conference Paper

Static data structure lower bounds imply rigidity

• Zeev Dvir
• Alexander Golovnev
• Omri Weinstein

We show that static data structure lower bounds in the group (linear) model imply semi-explicit lower bounds on matrix rigidity. In particular, we prove that an explicit lower bound of t ≥ ω(log 2 n ) on the cell-probe complexity of linear data structures in the group model, even against arbitrarily small linear space ( s = (1+) n ), would already imply a semi-explicit ( P NP ) construction of rigid matrices with significantly better parameters than the current state of art (Alon, Panigrahy and Yekhanin, 2009). Our results further assert that polynomial ( t ≥ n δ ) data structure lower bounds against near-optimal space, would imply super-linear circuit lower bounds for log-depth linear circuits (a four-decade open question). In the succinct space regime ( s = n + o ( n )), we show that any improvement on current cell-probe lower bounds in the linear model would also imply new rigidity bounds. Our results rely on a new connection between the “inner” and “outer” dimensions of a matrix (Paturi and Pudlák, 2006), and on a new reduction from worst-case to average-case rigidity, which is of independent interest.

STOC Conference 2015 Conference Paper

2-Server PIR with Sub-Polynomial Communication

• Zeev Dvir
• Sivakanth Gopi

A 2-server Private Information Retrieval (PIR) scheme allows a user to retrieve the ith bit of an n-bit database replicated among two non-communicating servers, while not revealing any information about i to either server. In this work we construct a 2-server PIR scheme with total communication cost n O√(log log n)/(log n) . This improves over current 2-server protocols which all require Ω(n 1/3 ) communication. Our construction circumvents the n 1/3 barrier of Razborov and Yekhanin which holds for the restricted model of bilinear group-based schemes (covering all previous 2-server schemes). The improvement comes from reducing the number of servers in existing protocols, based on Matching Vector Codes, from 3 or 4 servers to 2. This is achieved by viewing these protocols in an algebraic way (using polynomial interpolation) and extending them using partial derivatives.

STOC Conference 2014 Conference Paper

Breaking the quadratic barrier for 3-LCC's over the reals

• Zeev Dvir
• Shubhangi Saraf
• Avi Wigderson

We prove that 3-query linear locally correctable codes over the Reals of dimension d require block length n > d 2+ λ for some fixed, positive λ > 0. Geometrically, this means that if n vectors in R d are such that each vector is spanned by a linear number of disjoint triples of others, then it must be that n > d 2+ λ . This improves the known quadratic lower bounds (e.g. [20, 28]). While a modest improvement, we expect that the new techniques introduced in this work will be useful for further progress on lower bounds of locally correctable and decodable codes with more than 2 queries. At a high level, our proof has two parts, clustering and random restriction . The clustering step uses a powerful geometric theorem of Barthe which finds a basis change (and rescaling) putting the code in nearly isotropic position. This together with the fact that any LCC must have many 'correlated' pairs of points, lets us deduce that the vectors must have a surprisingly strong geometric clustering, and hence also combinatorial clustering with respect to the spanning triples. In the restriction step, we devise a new variant of the dimension reduction technique used in previous lower bounds, which is able to take advantage of the combinatorial clustering structure above. The analysis of our random projection method reduces to a simple (weakly) random graph process, and works over any field.

STOC Conference 2013 Conference Paper

New bounds for matching vector families

• Abhishek Bhowmick 0001
• Zeev Dvir
• Shachar Lovett

STOC Conference 2012 Conference Paper

Separating multilinear branching programs and formulas

• Zeev Dvir
• Guillaume Malod
• Sylvain Perifel
• Amir Yehudayoff

This work deals with the power of linear algebra in the context of multilinear computation. By linear algebra we mean algebraic branching programs (ABPs) which are known to be computationally equivalent to two basic tools in linear algebra: iterated matrix multiplication and the determinant. We compare the computational power of multilinear ABPs to that of multilinear arithmetic formulas, and prove a tight super-polynomial separation between the two models. Specifically, we describe an explicit n -variate polynomial F that is computed by a linear-size multilinear ABP but every multilinear formula computing F must be of size n Ω(log n) .

STOC Conference 2012 Conference Paper

Subspace evasive sets

• Zeev Dvir
• Shachar Lovett

We construct explicit subspace-evasive sets. These are subsets of F n of size |F| (1-ε)n whose intersection with any k-dimensional subspace is bounded by a constant c(k,ε). This problem was raised by Guruswami (CCC 2011) as it leads to optimal rate list-decodable codes of constant list size. The main technical ingredient is the construction of k low-degree polynomials whose common set of zeros has small intersection with any k-dimensional subspace.

STOC Conference 2011 Conference Paper

Rank bounds for design matrices with applications toc ombinatorial geometry and locally correctable codes

• Boaz Barak
• Zeev Dvir
• Amir Yehudayoff
• Avi Wigderson

FOCS Conference 2011 Conference Paper

Tight Lower Bounds for 2-query LCCs over Finite Fields

• Arnab Bhattacharyya 0001
• Zeev Dvir
• Amir Shpilka
• Shubhangi Saraf

A Locally Correctable Code (LCC) is an error correcting code that has a probabilistic self-correcting algorithm that, with high probability, can correct any coordinate of the codeword by looking at only a few other coordinates, even if a fraction δ of the coordinates are corrupted. LCCs are a stronger form of LDCs (Locally Decodable Codes) which have received a lot of attention recently due to their many applications and surprising constructions. In this work we show a separation between 2-query LDCs and LCCs over finite fields of prime order. Specifically, we prove a lower bound of the form p^{Ω(δd)} on the length of linear 2-query LCCs over $\F_p$, that encode messages of length d. Our bound improves over the known bound of $2^{Ω(δd)} \cite{GKST06, KdW04, DS07} which is tight for LDCs. Our proof makes use of tools from additive combinatorics which have played an important role in several recent results in theoretical computer science. Corollaries of our main theorem are new incidence geometry results over finite fields. The first is an improvement to the Sylvester-Gallai theorem over finite fields \cite{SS10} and the second is a new analog of Beck's theorem over finite fields.

FOCS Conference 2010 Conference Paper

Matching Vector Codes

• Zeev Dvir
• Parikshit Gopalan
• Sergey Yekhanin

A locally decodable code encodes a message by a codeword, such that even if the codeword is corrupted by noise, each message bit can be recovered with high probability by a randomized decoding procedure that reads only few bits of the codeword. Recently a new class of locally decodable codes, based on families of vectors with restricted dot products has been discovered. We refer to those codes as Matching Vector (MV) codes. In this work we develop a new view of MV codes and uncover certain similarities between them and classical Reed Muller codes. Our view allows us to obtain a deeper insight into the power and limitations of MV codes. We use it to construct codes that can tolerate more errors or are shorter than previously known codes for certain parameter settings. We also show super-linear lower bounds on the codeword length of any MV code.

FOCS Conference 2009 Conference Paper

Extensions to the Method of Multiplicities, with Applications to Kakeya Sets and Mergers

• Zeev Dvir
• Swastik Kopparty
• Shubhangi Saraf
• Madhu Sudan 0001

We extend the "method of multiplicities" to get the following results, of interest in combinatorics and randomness extraction. 1) We show that every Kakeya set (a set of points that contains a line in every direction) in F q n must be of size at least q n /2 n. This bound is tight to within a 2 + o(1) factor for every n as q? ?, compared to previous bounds that were off by exponential factors in n. 2) We give an improved construction of "randomness mergers". Mergers are seeded functions that take as input? (possibly correlated) random variables in {0, 1} N and a short random seed, and output a single random variable in {0, 1} N that is statistically close to having entropy (1 -?)? N when one of the? input variables is distributed uniformly. The seed we require is only (1/?)? log? -bits long, which significantly improves upon previous construction of mergers. 3) We show how to construct randomness extractors that use logarithmic length seeds while extracting 1 - o(1) fraction of the min-entropy of the source. Previous results could extract only a constant fraction of the entropy while maintaining logarithmic seed length. The "method of multiplicities", as used in prior work, analyzed subsets of vector spaces over finite fields by constructing somewhat low degree interpolating polynomials that vanish on every point in the subset with high multiplicity. The typical use of this method involved showing that the interpolating polynomial also vanished on some points outside the subset, and then used simple bounds on the number of zeroes to complete the analysis. Our augmentation to this technique is that we prove, under appropriate conditions, that the interpolating polynomial vanishes with high multiplicity outside the set. This novelty leads to significantly tighter analyses. To develop the extended method of multiplicities we provide a number of basic technical results about multiplicity of zeroes of polynomials that may be of general use. For instance, we strengthen the Schwartz-Zippel lemma to show that the expected multiplicity of zeroes of a non-zero degree d polynomial at a random point in S n, for any finite subset S of the underlying field, is at most d/|S|.

STOC Conference 2008 Conference Paper

Hardness-randomness tradeoffs for bounded depth arithmetic circuits

• Zeev Dvir
• Amir Shpilka
• Amir Yehudayoff

In this paper we show that lower bounds for bounded depth arithmetic circuits imply derandomization of polynomial identity testing for bounded depth arithmetic circuits. More formally, if there exists an explicit polynomial f(x 1 ,...,x m ) that cannot be computed by a depth d arithmetic circuit of small size then there exists an efficient deterministic algorithm to test whether a given depth d-8 circuit is identically zero or not (assuming the individual degrees of the tested circuit are not too high). In particular, if we are guaranteed that the circuit computes a multilinear polynomial then we can perform the identity test efficiently. To the best of our knowledge this is the first hardness-randomness tradeoff for bounded depth arithmetic circuits. The above results are obtained using the arithmetic Nisan-Wigderson generator of Impagliazzo and Kabanets together with a new theorem on bounded depth circuits, which is the main technical contribution of our work. This theorem deals with polynomial equations of the form P(x 1 ,...,x n ,y) ≡ 0 and shows that if P has a circuit of depth d and size s and if the polynomial f(x 1 ,...,x n ) satisfies P(x 1 ,...,x n ,f(x 1 ,...,x n ))≡ 0 then f has a circuit of depth d+3 and size O(s • r + m r ), where m is the degree of f and r is the highest degree of the variable y appearing in P. In the other direction we observe that the methods of Impagliazzo and Kabanets imply that if we can derandomize polynomial identity testing for bounded depth circuits then NEXP does not have bounded depth arithmetic circuits. That is, either NEXP ⊄ P/poly or the Permanent is not computable by polynomial size bounded depth arithmetic circuits.

FOCS Conference 2008 Conference Paper

Kakeya Sets, New Mergers and Old Extractors

• Zeev Dvir
• Avi Wigderson

A merger is a probabilistic procedure which extracts the randomness out of any (arbitrarily correlated) set of random variables, as long as one of them is uniform. Our main result is an efficient, simple, optimal (to constant factors) merger, which, for k random vairables on n bits each, uses a O(log(nk)) seed, and whose error is 1/nk. Our merger can be viewed as a derandomized version of the merger of Lu, Reingold, Vadhan and Wigderson (2003). Its analysis generalizes the recent resolutionof the Kakeya problem in finite fields of Dvir (2008). Following the plan set forth by Ta-Shma (1996), who defined mergers as part of this plan, our merger provides the last "missing link" to a simple and modular construction of extractors for all entropies, which is optimal to constant factorsin all parameters. This complements the elegant construction of optimal extractor by Guruswami, Vadhan and Umans (2007). We also give simple extensions of our merger in two directions. First, we generalize it to handle the case where no source is uniform - in that case the merger will extract the entropy present in the most random of the given sources. Second, we observe that the merger works just as well in the computational setting, when the sources are efficiently samplable, and computational notions of entropy replace the information theoretic ones.

FOCS Conference 2007 Conference Paper

Extractors and Rank Extractors for Polynomial Sources

• Zeev Dvir
• Ariel Gabizon
• Avi Wigderson

In this paper we construct explicit deterministic extractors from polynomial sources, namely from distributions sampled by low degree multivariate polynomials over finite fields. This naturally generalizes previous work on extraction from affine sources. A direct consequence is a deterministic extractor for distributions sampled by polynomial size arithmetic circuits over exponentially large fields. The first step towards extraction is a construction o/rank extractors, which are polynomial mappings that "extract" the algebraic rank from any system of low degree polynomials. More precisely, for any n polynomials, k of which are algebraically independent, a rank extractor outputs k algebraically independent polynomials of slightly higher degree. A result of Wooley allows us to relate algebraic rank and min-entropy and to show that a rank extractor is also a high quality condenser for polynomial sources over polynomially large fields. Finally, to turn this condenser into an extractor, we employ a theorem of Bombieri, giving a character sum estimate for polynomials defined over curves. It allows extracting all the randomness (up to a multiplicative constant) from polynomial sources over exponentially large fields.

STOC Conference 2005 Conference Paper

Locally decodable codes with 2 queries and polynomial identity testing for depth 3 circuits

• Zeev Dvir
• Amir Shpilka

In this work we study two, seemingly unrelated, notions. Locally Decodable Codes (LDCs) are codes that allow the recovery of each message bit from a constant number of entries of the codeword. Polynomial Identity Testing (PIT) is one of the fundamental problems of algebraic complexity: we are given a circuit computing a multivariate polynomial and we have to determine whether the polynomial is identically zero. We improve known results on locally decodable codes and on polynomial identity testing and show a relation between the two notions. In particular we obtain the following results: We show that if E: Fn → Fm is a linear LDC with 2 queries then m = exp(Ω(n)). Previously this was only known for fields of size << 2n [18]. We show that from every depth 3 arithmetic circuit (ΣΠΣ circuit), C, with a bounded (constant) top fan-in that computes the zero polynomial, one can construct a locally decodeable code. More formally: Assume that C is minimal (no subset of the multiplication gates sums to zero) and simple (no linear function appears in all the multiplication gates). Denote by d the degree of the polynomial computed by C and by r the rank of the linear functions appearing in C. Then we can construct a linear LDC with 2 queries, that encodes messages of length r/polylog(d) by codewords of length O(d). We prove a structural theorem for ΣΠΣ circuits, with a bounded top fan-in, that compute the zero polynomial. In particular we show that if such a circuit is simple and minimal and of polynomial size then its rank, r, is only polylogarithmic in the number of variables (a priory it could have been linear). We give new PIT algorithms for ΣΠΣ circuits with a bounded top fan-in:A deterministic algorithm that runs in quasi polynomial time.A randomized algorithm that runs in polynomial time and uses only polylogarithmic number of random bits.