Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Zeev Dvir:

TR14-094 | 24th July 2014
Zeev Dvir, Sivakanth Gopi

2-Server PIR with sub-polynomial communication

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

TR14-056 | 18th April 2014
Zeev Dvir, Rafael Mendes de Oliveira

Factors of Sparse Polynomials are Sparse

Revisions: 1 , Comments: 1

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

TR14-026 | 27th February 2014
Jop Briet, Zeev Dvir, Guangda Hu, Shubhangi Saraf

Lower Bounds for Approximate LDCs

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

TR14-010 | 23rd January 2014
Jean Bourgain, Zeev Dvir, Ethan Leeman

Affine extractors over large fields with exponential error

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

TR14-003 | 10th January 2014
Zeev Dvir, Rafael Mendes de Oliveira, Amir Shpilka

Testing Equivalence of Polynomials under Shifts

Revisions: 2 , Comments: 1

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

TR13-160 | 20th November 2013
Zeev Dvir, Shubhangi Saraf, Avi Wigderson

Breaking the quadratic barrier for 3-LCCs over the Reals

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

TR13-061 | 17th April 2013
Zeev Dvir, Guangda Hu

Matching-Vector Families and LDCs Over Large Modulo

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

TR12-139 | 2nd November 2012
Albert Ai, Zeev Dvir, Shubhangi Saraf, Avi Wigderson

Sylvester-Gallai type theorems for approximate collinearity

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

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

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

TR12-034 | 5th April 2012
Abhishek Bhowmick, Zeev Dvir, Shachar Lovett

New Lower Bounds for Matching Vector Codes

Revisions: 5

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

TR11-160 | 1st December 2011
Zeev Dvir, Anup Rao, Avi Wigderson, Amir Yehudayoff

Restriction Access

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

TR11-139 | 26th October 2011
Zeev Dvir, Shachar Lovett

Subspace Evasive Sets

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

TR11-134 | 9th October 2011
Zeev Dvir, Guillaume Malod, Sylvain Perifel, Amir Yehudayoff

Separating multilinear branching programs and formulas

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

TR11-054 | 13th April 2011
Arnab Bhattacharyya, Zeev Dvir, Shubhangi Saraf, Amir Shpilka

Tight lower bounds for 2-query LCCs over finite fields

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

TR10-160 | 28th October 2010
Zeev Dvir, Dan Gutfreund, Guy Rothblum, Salil Vadhan

On Approximating the Entropy of Polynomial Mappings

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.

... more >>>

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

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

TR10-012 | 27th January 2010
Zeev Dvir, Parikshit Gopalan, Sergey Yekhanin

Matching Vector Codes

Revisions: 1

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

TR09-135 | 10th December 2009
Zeev Dvir, Avi Wigderson

Monotone expanders - constructions and applications

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

TR09-134 | 10th December 2009
Zeev Dvir

On matrix rigidity and locally self-correctable codes

Revisions: 1

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

TR09-077 | 16th September 2009
Zeev Dvir

From Randomness Extraction to Rotating Needles

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

TR09-070 | 1st September 2009
Andrej Bogdanov, Zeev Dvir, Elad Verbin, Amir Yehudayoff

Pseudorandomness for Width 2 Branching Programs

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

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

We extend the ``method of multiplicities'' to get the following results, of interest in combinatorics and randomness extraction.
\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 >>>

TR08-058 | 1st June 2008
Zeev Dvir, Avi Wigderson

Kakeya sets, new mergers and old extractors

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

TR08-042 | 6th April 2008
Zeev Dvir

Deterministic Extractors for Algebraic Sources

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

TR08-004 | 2nd January 2008
Zeev Dvir, Amir Shpilka

Noisy Interpolating Sets for Low Degree Polynomials

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

TR07-122 | 22nd November 2007
Zeev Dvir, Amir Shpilka

Towards Dimension Expanders Over Finite Fields

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

TR07-121 | 21st November 2007
Zeev Dvir, Amir Shpilka, Amir Yehudayoff

Hardness-Randomness Tradeoffs for Bounded Depth Arithmetic Circuits

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

TR07-056 | 10th July 2007
Zeev Dvir, Ariel Gabizon, Avi Wigderson

Extractors and Rank Extractors for Polynomial Sources

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

TR05-067 | 28th June 2005
Zeev Dvir, Amir Shpilka

An Improved Analysis of Mergers

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

TR05-044 | 6th April 2005
Zeev Dvir, Amir Shpilka

Locally Decodable Codes with 2 queries and Polynomial Identity Testing for depth 3 circuits

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

TR05-025 | 20th February 2005
Zeev Dvir, Ran Raz

Analyzing Linear Mergers

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

ISSN 1433-8092 | Imprint