All reports by Author Zeev Dvir:

__
TR22-047
| 4th April 2022
__

Manik Dhar, Zeev Dvir#### Linear Hashing with $\ell_\infty$ guarantees and two-sided Kakeya bounds

Revisions: 1

__
TR19-129
| 27th September 2019
__

Zeev Dvir, Allen Liu#### Fourier and Circulant Matrices are Not Rigid

__
TR18-188
| 7th November 2018
__

Zeev Dvir, Alexander Golovnev, Omri Weinstein#### Static Data Structure Lower Bounds Imply Rigidity

Revisions: 2

__
TR14-094
| 24th July 2014
__

Zeev Dvir, Sivakanth Gopi#### 2-Server PIR with sub-polynomial communication

__
TR14-056
| 18th April 2014
__

Zeev Dvir, Rafael Mendes de Oliveira#### Factors of Sparse Polynomials are Sparse

Revisions: 1
,
Comments: 1

__
TR14-026
| 27th February 2014
__

Jop Briet, Zeev Dvir, Guangda Hu, Shubhangi Saraf#### Lower Bounds for Approximate LDCs

__
TR14-010
| 23rd January 2014
__

Jean Bourgain, Zeev Dvir, Ethan Leeman#### Affine extractors over large fields with exponential error

__
TR14-003
| 10th January 2014
__

Zeev Dvir, Rafael Mendes de Oliveira, Amir Shpilka#### Testing Equivalence of Polynomials under Shifts

Revisions: 2
,
Comments: 1

__
TR13-160
| 20th November 2013
__

Zeev Dvir, Shubhangi Saraf, Avi Wigderson#### Breaking the quadratic barrier for 3-LCCs over the Reals

__
TR13-061
| 17th April 2013
__

Zeev Dvir, Guangda Hu#### Matching-Vector Families and LDCs Over Large Modulo

__
TR12-139
| 2nd November 2012
__

Albert Ai, Zeev Dvir, Shubhangi Saraf, Avi Wigderson#### Sylvester-Gallai type theorems for approximate collinearity

__
TR12-138
| 2nd November 2012
__

Zeev Dvir, Shubhangi Saraf, Avi Wigderson#### Improved rank bounds for design matrices and a new proof of Kelly's theorem

__
TR12-034
| 5th April 2012
__

Abhishek Bhowmick, Zeev Dvir, Shachar Lovett#### New Lower Bounds for Matching Vector Codes

Revisions: 5

__
TR11-160
| 1st December 2011
__

Zeev Dvir, Anup Rao, Avi Wigderson, Amir Yehudayoff#### Restriction Access

__
TR11-139
| 26th October 2011
__

Zeev Dvir, Shachar Lovett#### Subspace Evasive Sets

__
TR11-134
| 9th October 2011
__

Zeev Dvir, Guillaume Malod, Sylvain Perifel, Amir Yehudayoff#### Separating multilinear branching programs and formulas

__
TR11-054
| 13th April 2011
__

Arnab Bhattacharyya, Zeev Dvir, Shubhangi Saraf, Amir Shpilka#### Tight lower bounds for 2-query LCCs over finite fields

__
TR10-160
| 28th October 2010
__

Zeev Dvir, Dan Gutfreund, Guy Rothblum, Salil Vadhan#### On Approximating the Entropy of Polynomial Mappings

__
TR10-149
| 22nd September 2010
__

Boaz Barak, Zeev Dvir, Avi Wigderson, Amir Yehudayoff#### Rank Bounds for Design Matrices with Applications to Combinatorial Geometry and Locally Correctable Codes

Revisions: 1

__
TR10-012
| 27th January 2010
__

Zeev Dvir, Parikshit Gopalan, Sergey Yekhanin#### Matching Vector Codes

Revisions: 1

__
TR09-135
| 10th December 2009
__

Zeev Dvir, Avi Wigderson#### Monotone expanders - constructions and applications

__
TR09-134
| 10th December 2009
__

Zeev Dvir#### On matrix rigidity and locally self-correctable codes

Revisions: 1

__
TR09-077
| 16th September 2009
__

Zeev Dvir#### From Randomness Extraction to Rotating Needles

__
TR09-070
| 1st September 2009
__

Andrej Bogdanov, Zeev Dvir, Elad Verbin, Amir Yehudayoff#### Pseudorandomness for Width 2 Branching Programs

__
TR09-004
| 15th January 2009
__

Zeev Dvir, Swastik Kopparty, Shubhangi Saraf, Madhu Sudan#### Extensions to the Method of Multiplicities, with applications to Kakeya Sets and Mergers

Revisions: 2

__
TR08-058
| 1st June 2008
__

Zeev Dvir, Avi Wigderson#### Kakeya sets, new mergers and old extractors

__
TR08-042
| 6th April 2008
__

Zeev Dvir#### Deterministic Extractors for Algebraic Sources

__
TR08-004
| 2nd January 2008
__

Zeev Dvir, Amir Shpilka#### Noisy Interpolating Sets for Low Degree Polynomials

__
TR07-122
| 22nd November 2007
__

Zeev Dvir, Amir Shpilka#### Towards Dimension Expanders Over Finite Fields

__
TR07-121
| 21st November 2007
__

Zeev Dvir, Amir Shpilka, Amir Yehudayoff#### Hardness-Randomness Tradeoffs for Bounded Depth Arithmetic Circuits

__
TR07-056
| 10th July 2007
__

Zeev Dvir, Ariel Gabizon, Avi Wigderson#### Extractors and Rank Extractors for Polynomial Sources

__
TR05-067
| 28th June 2005
__

Zeev Dvir, Amir Shpilka#### An Improved Analysis of Mergers

__
TR05-044
| 6th April 2005
__

Zeev Dvir, Amir Shpilka#### Locally Decodable Codes with 2 queries and Polynomial Identity Testing for depth 3 circuits

__
TR05-025
| 20th February 2005
__

Zeev Dvir, Ran Raz#### Analyzing Linear Mergers

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 \to \mathbb{F}_q^t$ with $q^t$ taken to be sufficiently smaller than $|S|$. Let ... more >>>

Zeev Dvir, Allen Liu

The concept of matrix rigidity was first introduced by Valiant in [Val77]. Roughly speaking, a matrix is rigid if its rank cannot be reduced significantly by changing a small number of entries. There has been extensive interest in rigid matrices as Valiant showed that rigidity can be used to prove ... more >>>

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 \geq \omega(\log^2 n)$ on the cell-probe complexity of linear data structures in the group model, even against arbitrarily small ... more >>>

Zeev Dvir, Sivakanth Gopi

A 2-server Private Information Retrieval (PIR) scheme allows a user to retrieve the $i$th bit of an $n$-bit database replicated among two servers (which do not communicate) while not revealing any information about $i$ to either server. In this work we construct a 1-round 2-server PIR with total communication cost ... more >>>

Zeev Dvir, Rafael Mendes de Oliveira

We show that if $f(x_1,\ldots,x_n)$ is a polynomial with $s$ monomials and $g(x_1,\ldots,x_n)$ divides $f$ then $g$

has at most $\max(s^{O(\log s \log\log s)},d^{O(\log d)})$ monomials, where $d$ is a bound on the individual degrees

of $f$. This answers a question of von zur Gathen and Kaltofen (JCSS ...
more >>>

Jop Briet, Zeev Dvir, Guangda Hu, Shubhangi Saraf

We study an approximate version of $q$-query LDCs (Locally Decodable Codes) over the real numbers and prove lower bounds on the encoding length of such codes. A $q$-query $(\alpha,\delta)$-approximate LDC is a set $V$ of $n$ points in $\mathbb{R}^d$ so that, for each $i \in [d]$ there are $\Omega(\delta n)$ ... more >>>

Jean Bourgain, Zeev Dvir, Ethan Leeman

We describe a construction of explicit affine extractors over large finite fields with exponentially small error and linear output length. Our construction relies on a deep theorem of Deligne giving tight estimates for exponential sums over smooth varieties in high dimensions.

more >>>Zeev Dvir, Rafael Mendes de Oliveira, Amir Shpilka

Two polynomials $f, g \in F[x_1, \ldots, x_n]$ are called shift-equivalent if there exists a vector $(a_1, \ldots, a_n) \in {F}^n$ such that the polynomial identity $f(x_1+a_1, \ldots, x_n+a_n) \equiv g(x_1,\ldots,x_n)$ holds. Our main result is a new randomized algorithm that tests whether two given polynomials are shift equivalent. Our ... more >>>

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+\lambda}$ for some fixed, positive $\lambda >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 ... more >>>

Zeev Dvir, Guangda Hu

We prove new upper bounds on the size of families of vectors in $\Z_m^n$ with restricted modular inner products, when $m$ is a large integer. More formally, if $\vec{u}_1,\ldots,\vec{u}_t \in \Z_m^n$ and $\vec{v}_1,\ldots,\vec{v}_t \in \Z_m^n$ satisfy $\langle\vec{u}_i,\vec{v}_i\rangle\equiv0\pmod m$ and $\langle\vec{u}_i,\vec{v}_j\rangle\not\equiv0\pmod m$ for all $i\neq j\in[t]$, we prove that $t \leq ... more >>>

Albert Ai, Zeev Dvir, Shubhangi Saraf, Avi Wigderson

We study questions in incidence geometry where the precise position of points is `blurry' (e.g. due to noise, inaccuracy or error). Thus lines are replaced by narrow tubes, and more generally affine subspaces are replaced by their small neighborhood. We show that the presence of a sufficiently large number of ... more >>>

Zeev Dvir, Shubhangi Saraf, Avi Wigderson

We study the rank of complex sparse matrices in which the supports of different columns have small intersections. The rank of these matrices, called design matrices, was the focus of a recent work by Barak et. al. (BDWY11) in which they were used to answer questions regarding point configurations. In ... more >>>

Abhishek Bhowmick, Zeev Dvir, Shachar Lovett

We prove new lower bounds on the encoding length of Matching Vector (MV) codes. These recently discovered families of Locally Decodable Codes (LDCs) originate in the works of Yekhanin [Yek] and Efremenko [Efr] and are the only known families of LDCs with a constant number of queries and sub-exponential encoding ... more >>>

Zeev Dvir, Anup Rao, Avi Wigderson, Amir Yehudayoff

We introduce a notion of non-black-box access to computational devices (such as circuits, formulas, decision trees, and so forth) that we call \emph{restriction access}. Restrictions are partial assignments to input variables. Each restriction simplifies the device, and yields a new device for the restricted function on the unassigned variables. On ... more >>>

Zeev Dvir, Shachar Lovett

In this work we describe an explicit, simple, construction of large subsets of F^n, where F is a finite field, that have small intersection with every k-dimensional affine subspace. Interest in the explicit construction of such sets, termed subspace-evasive sets, started in the work of Pudlak and Rodl (2004) ... more >>>

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 ... more >>>

Arnab Bhattacharyya, Zeev Dvir, Shubhangi Saraf, Amir Shpilka

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 $\delta$ of the

coordinates are corrupted. LCC's are a stronger form ...
more >>>

Zeev Dvir, Dan Gutfreund, Guy Rothblum, Salil Vadhan

We investigate the complexity of the following computational problem:

Polynomial Entropy Approximation (PEA):

Given a low-degree polynomial mapping

$p : F^n\rightarrow F^m$, where $F$ is a finite field, approximate the output entropy

$H(p(U_n))$, where $U_n$ is the uniform distribution on $F^n$ and $H$ may be any of several entropy measures.

Boaz Barak, Zeev Dvir, Avi Wigderson, Amir Yehudayoff

A $(q,k,t)$-design matrix is an m x n matrix whose pattern of zeros/non-zeros satisfies the following design-like condition: each row has at most $q$ non-zeros, each column has at least $k$ non-zeros and the supports of every two columns intersect in at most t rows. We prove that the rank ... more >>>

Zeev Dvir, Parikshit Gopalan, Sergey Yekhanin

An $(r,\delta,\epsilon)$-locally decodable code encodes a $k$-bit message $x$ to an $N$-bit codeword $C(x),$ such that for every $i\in [k],$ the $i$-th message bit can be recovered with probability $1-\epsilon,$ by a randomized decoding procedure that reads only $r$ bits, even if the codeword $C(x)$ is corrupted in up to ... more >>>

Zeev Dvir, Avi Wigderson

The main purpose of this work is to formally define monotone expanders and motivate their study with (known and new) connections to other graphs and to several computational and pseudorandomness problems. In particular we explain how monotone expanders of constant degree lead to:

(1) Constant degree dimension expanders in finite ...
more >>>

Zeev Dvir

We describe a new approach for the problem of finding {\rm rigid} matrices, as posed by Valiant [Val77], by connecting it to the, seemingly unrelated, problem of proving lower bounds for locally self-correctable codes. This approach, if successful, could lead to a non-natural property (in the sense of Razborov and ... more >>>

Zeev Dvir

The finite field Kakeya problem deals with the way lines in different directions can overlap in a vector space over a finite field. This problem came up in the study of certain Euclidean problems and, independently, in the search for explicit randomness extractors. We survey recent progress on this problem ... more >>>

Andrej Bogdanov, Zeev Dvir, Elad Verbin, Amir Yehudayoff

Bogdanov and Viola (FOCS 2007) constructed a pseudorandom

generator that fools degree $k$ polynomials over $\F_2$ for an arbitrary

constant $k$. We show that such generators can also be used to fool branching programs of width 2 and polynomial length that read $k$ bits of inputs at a

time. This ...
more >>>

Zeev Dvir, Swastik Kopparty, Shubhangi Saraf, Madhu Sudan

We extend the ``method of multiplicities'' to get the following results, of interest in combinatorics and randomness extraction.

\begin{enumerate}

\item We show that every Kakeya set in $\F_q^n$, the $n$-dimensional vector space over the finite field on $q$ elements, must be of size at least $q^n/2^n$. This bound is tight ...
more >>>

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 ...
more >>>

Zeev Dvir

An algebraic source is a random variable distributed

uniformly over the set of common zeros of one or more multivariate

polynomials defined over a finite field $F$. Our main result is

the construction of an explicit deterministic extractor for

algebraic sources over exponentially large prime fields. More

precisely, we give ...
more >>>

Zeev Dvir, Amir Shpilka

A Noisy Interpolating Set (NIS) for degree $d$ polynomials is a

set $S \subseteq \F^n$, where $\F$ is a finite field, such that

any degree $d$ polynomial $q \in \F[x_1,\ldots,x_n]$ can be

efficiently interpolated from its values on $S$, even if an

adversary corrupts a constant fraction of the values. ...
more >>>

Zeev Dvir, Amir Shpilka

In this paper we study the problem of explicitly constructing a

{\em dimension expander} raised by \cite{BISW}: Let $\mathbb{F}^n$

be the $n$ dimensional linear space over the field $\mathbb{F}$.

Find a small (ideally constant) set of linear transformations from

$\F^n$ to itself $\{A_i\}_{i \in I}$ such that for every linear

more >>>

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 ... more >>>

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 (which are degree 1 polynomials). A direct consequence is a deterministic extractor for distributions sampled by polynomial ... more >>>

Zeev Dvir, Amir Shpilka

Mergers are functions that transform k (possibly dependent) random sources into a single random source, in a way that ensures that if one of the input sources has min-entropy rate $\delta$ then the output has min-entropy rate close to $\delta$. Mergers have proven to be a very useful tool in ... more >>>

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 ... more >>>

Zeev Dvir, Ran Raz

random sources into a single random source, in a way that ensures

that if one of the input sources has min-entropy rate $\delta$

then the output has min-entropy rate close to $\delta$. Mergers

have proven to be a very useful tool in ...
more >>>