Matching-Vector Families and LDCs Over Large Modulo,
Z. Dvir and G. Hu.
2013.
Manuscript.
[ bib |
.pdf ]
We prove an improved upper bound of O(mn/2+ 8.47) on the size of Matching-Vector families in Zmn with m an arbitrary composite. This improves the bound mn/2 + O(logm) proved in [BDL13] and is tight up to the constant 8.47 when m is sufficiently larger than n. As a corollary, we show that Matching-Vector codes [DGY11] have encoding length at least K19/18 for messages of length K.
Incidence Theorems and Their Applications.
Z. Dvir.
Foundations and Trends in Theoretical Computer Science,
6(4):257-393, 2012.
[ bib |
.pdf ]
A survey paper covering recent progress on geometric incidence theorems and their applications in theoretical CS. The topics include Szemeredi-Trotter type theorems, the solution to Erdos distance problem by Guth and Katz, The Kakeya conjecture over the reals and over finite fields and locally correctable codes.
Fractional Sylvester-Gallai theorems.
B. Barak, Z. Dvir, A. Wigderson, and A. Yehudayoff.
Proceedings of the National Academy of Sciences, 2012.
(journal version of STOC 11 paepr).
[ bib |
.pdf ]
The existence of many collinear triples in a set of points is used to bound the dimension of the space spanned by the points. The main technical tool is a rank bound for matrices whose support is a combinatorial design. This is the Journal version of a STOC 11' paper by the same authors.
Sylvester-Gallai theorems for approximate collinearity,
A. Ai, Z. Dvir, S. Saraf, and A. Wigderson.
2012.
Manuscript.
[ bib |
.pdf ]
We extend the results of [BDWY] to settings in which a set of points contains many approximately collinear triples. This results in a low dimensional subspace that approximates the entire set to within a small ε.
Improved rank bounds for design matrices and a new proof of
Kelly's theorem., Z. Dvir, S. Saraf, and A. Wigderson.
2012.
Manuscript.
[ bib |
.pdf ]
Building on the framework of [BDWY] we give tighter dimension bounds for design matrices and related point configurations. A new proof of Kelly's theorem (the complex version of Sylvester-Gallai) is obtained as a result.
New Bounds for Matching Vector Families, A. Bhowmick,
Z. Dvir, and S. Lovett.
2013.
STOC 2013 (to appear).
[ bib |
.pdf ]
We prove new upper bounds for families of vectors in Zmn with restricted dot products mod m. Such families, called Matching-Vector Families, are used in the construction of locally decodable codes (see “Matching Vector Codes” below) and these new bounds shed light on the limitations of these constructions.
Variety Evasive Sets, Z. Dvir, J. Kollár, and S. Lovett.
2012.
To appear in Comp. Complex.
[ bib |
.pdf ]
For given k,n,d, we give an explicit construction of a large set S in Fn, where F is a large finite field, such that S has small intersection with every variety V of degree d and dimension k. This extends the work done in “Subspace evasive sets” (see below) for degree one varieties (or affine subspaces).
Subspace evasive sets.
Z. Dvir and S. Lovett.
In Proceedings of the 44th symposium on Theory of
Computing, STOC '12, pages 351-358. ACM, New York, NY, USA, 2012.
[ bib |
.pdf ]
We give an explicit construction of large sets that have small intersection with any subspace of given dimension k over a large finite field. This question was raised in a recent work of Guruswami who showed an application of such sets to improve the list size of rate-optimal lost-decodable codes.
Restriction access.
Z. Dvir, A. Rao, A. Wigderson, and A. Yehudayoff.
In ITCS, pages 19-33. 2012.
[ bib |
.pdf ]
We present a new learning model that `interpolates' between black-box (or query only) access and complete access to a computational device. In our model, the learner gets access to randomly chosen restrictions of the device (be it circuit, DNF or other) and the resulting simplified device. We give two new learning algorithms in this model for decision trees and DNFs under arbitrary distributions on inputs (PAC learning) and analyze their performance.
Separating multilinear branching programs and formulas.
Z. Dvir, G. Malod, S. Perifel, and A. Yehudayoff.
In Proceedings of the 44th symposium on Theory of
Computing, STOC '12, pages 615-624. ACM, New York, NY, USA, 2012.
[ bib |
.pdf ]
We give an explicit polynomial size multilinear ABP (arithmetic branching program) that cannot be computed by a polynomial size multilinear arithmetic formula. This extends previous work of Raz that separated multilinear circuits and formulas.
Tight Lower Bounds for 2-query LCCs over Finite Fields.
A. Bhattacharyya, Z. Dvir, A. Shpilka, and S. Saraf.
In Proc. of FOCS 2011, pages 638-647. 2011.
[ bib |
.pdf ]
We give asymptotically tight lower bounds on the encoding length of linear two-query Locally-Correctable Codes (LCCs) over prime finite fields. For a message of length k, we show that the length of the codeword has to be at least exp(k log(p)), where p is the field size. This improves on the previous known bound of exp(k) and shows a separation between linear LDCs (locally decodable codes) and LCCs over prime fields.
Rank bounds for design matrices with applications to
combinatorial geometry and locally correctable codes.
B. Barak, Z. Dvir, A. Yehudayoff, and A. Wigderson.
In Proceedings of the 43rd annual ACM symposium on Theory
of computing, STOC '11, pages 519-528. ACM, New York, NY, USA, 2011.
[ bib |
.pdf ]
We prove lower bounds on the rank of complex matrices whose support has properties of a combinatorial design. These result in new theorems bounding the dimension of point configurations with many local dependencies (e.g., three points on a line etc..) and 2-query LCCs over the complex numbers.
On approximating the entropy of polynomial mappings.
Z. Dvir, D. Gutfreund, G. Rothblum, and S. Vadhan.
In Proceedings of the Second Symposium on Innovations in
Computer Science (ICS 2011), Beijing, China, 7-9 January 2011, 2011.
[ bib |
.pdf ]
Given a polynomial map g from Fk to Fn, where F is a finite field, we study the question of estimating the entropy of g(U) with U distributed uniformly over Fk. We give both algorithms and hardness results for some settings of the parameters and discuss its relationship to other problems arising in cryptography.
Matching vector codes.
Z. Dvir, P. Gopalan, and S. Yekhanin.
SIAM J. Comput., 40:1154-1178, 2011.
(Extended abstract appeared in FOCS 2010).
[ bib |
.pdf ]
We establish a general framework for understanding recent new constructions of Locally-Decodable Codes (LDCs) arising from families of vectors with restricted modular dot products. In this framework, the codes are viewed as polynomial multivariate codes (Reed Muller) with high degree monomials chosen carefully among all monomials (so that restrictions to multiplicative lines have low degree). We use this framework to extend the construction from the constant query regime to an arbitrary number of queries.
Monotone Expanders: Constructions and Applications.
Z. Dvir and A. Wigderson.
Theory of Computing, 6(1):291-308, 2010.
[ bib |
.pdf ]
We construct expander graphs that have near-constant degree and that can be decomposed into a small number of `monotone', or order-preserving, partial mappings. We discuss the applications of such graphs to dimension expanders and to computational complexity of Turing machines.
On Matrix Rigidity and Locally Self-correctable Codes.
Z. Dvir.
Computational Complexity, 20(2):367-388, 2011.
(Extended abstract appeared in CCC 2010).
[ bib |
.pdf ]
We describe a reduction from the problem of constructing explicit rigid matrices to that of proving lower bounds on the encoding length of LCCs (Locally Correctable Codes) over any field.
From randomness extraction to rotating needles.
Z. Dvir.
SIGACT News, 40(4):46-61, 2009.
[ bib |
.pdf ]
This survey includes an overview of the finite field Kakeya problem, its solution and the applications to randomness extractors.
Extensions to the Method of Multiplicities, with applications
to Kakeya Sets and Mergers.
Z. Dvir, S. Kopparty, S. Saraf, and M. Sudan.
In Proceedings of the 50th Annual IEEE Symposium on
Foundations of Computer Science (FOCS), pages 181-190. IEEE Computer
Society, Washington, DC, USA, 2009.
[ bib |
.pdf ]
This work gives near-optimal bounds for the size of finite field Kakeya sets and, as a result, obtains the first randomness extractors with logarithmic seed-length and sub-linear entropy loss. The main technical contribution is an extension of the polynomial method (originally used to prove the finite field Kakeya conjecture) to use polynomials of unbounded degree together with high order partial derivatives.
Kakeya Sets, New Mergers, and Old Extractors.
Z. Dvir and A. Wigderson.
SIAM J. on Computing, 40(3):778-792, 2011.
(Extended abstract appeared in FOCS 2008).
[ bib |
.pdf ]
Extending the recent solution of the finite field Kakeya conjecture to handle high degree curves, we give new and simplified constructions of randomness extractors based on linear `mergers'.
On the size of Kakeya sets in finite fields.
Z. Dvir.
J. Amer. Math. Soc., 22:1093-1097, 2009.
[ bib |
.pdf ]
A proof of the finite field Kakeya conjecture raised by Wolff regarding the minimal size of a set containing a line in each direction over a finite field.
Extractors for varieties.
Z. Dvir.
computational complexity, 21:515-572, 2012.
(Conference version appeared in CCC 09).
[ bib |
.pdf ]
We describe an explicit map that outputs close-to-uniform random bits, whenever it is fed samples from a random distribution over an unknown algebraic variety of bounded degree over a finite field.
Pseudorandomness for Width 2 Branching Programs.
A. Bogdanov, Z. Dvir, E. Verbin, and A. Yehudayoff.
Theory of Computing, 9(7):283-293, 2013.
[ bib |
.pdf ]
A construction of pseudorandom generators for width-2 branching programs using high order Fourier analysis.
Noisy Interpolating Sets for Low-Degree Polynomials.
Z. Dvir and A. Shpilka.
Theory of Computing, 7(1):1-18, 2011.
(Extended abstract appeared in CCC 2008).
[ bib |
.pdf ]
An explicit construction of a set of points such that every low degree multivariate polynomial (over a finite field) can be reconstructed efficiently from its evaluations on this set, even in the presence of adversarial errors.
Hardness-randomness tradeoffs for bounded depth arithmetic
circuits.
Z. Dvir, A. Shpilka, and A. Yehudayoff.
SIAM J. Comput., 39(4):1279-1293, 2009.
(Extended abstract appeared in STOC '08).
[ bib |
.pdf ]
This paper extends the seminal work of Kabanetz and Impagliazzo, who showed a connection between Polynomial Identity Testing (PIT) and arithmetic circuit lower bounds, to the model of bounded depth arithmetic circuits.
Towards dimension expanders over finite fields.
Z. Dvir and A. Shpilka.
Combinatorica, 31:305-320, 2011.
(Extended abstract appeared at CCC '08).
[ bib |
.pdf ]
We show an explicit construction of a small number of linear maps from Fn to Fn, where F is a finite field, that `expand' the dimension of any subspace by a constant factor (the newer paper `monotone expanders' above gives a better construction for this problem).
Extractors And Rank Extractors For Polynomial Sources.
Z. Dvir, A. Gabizon, and A. Wigderson.
Comput. Complex., 18(1):1-58, 2009.
(Extended abstract appeared in FOCS '07).
[ bib |
.pdf ]
We construct an explicit map that `extracts' the entropy from any random source generated by a low degree polynomial mapping (applied on a uniform input). As a corollary, we get a deterministic extractor for sources sampled by small arithmetic circuits (over very large fields).
An Improved Analysis of Linear Mergers.
Z. Dvir and A. Shpilka.
Comput. Complex., 16(1):34-59, 2007.
(Extended abstract appeared in RANDOM '05).
[ bib |
.pdf ]
An improved analysis of the linear mergers proposed by Lu, Reingold, Vadhan and Wigderson using a connection to the finite field Kakeya problem.
Analyzing Linear Mergers.
Z. Dvir and R. Raz.
Random Structures and Algorithms, 32(3):334 - 345, 2007.
[ bib |
.pdf ]
An improved analysis of linear mergers obtaining a stronger control over the error.
Locally decodable codes with 2 queries and polynomial identity
testing for depth 3 circuits.
Z. Dvir and A. Shpilka.
SIAM J. on Computing, 36(5):1404-1434, 2006.
(Extended abstract appeared in STOC '05).
[ bib |
.pdf ]
A deterministic polynomial identity testing algorithm for depth 3 circuits with bounded top fan-in that runs in quai-polynomial time.
This file was generated by bibtex2html 1.96.