@unpublished{DH13,
author = {Z. Dvir and G. Hu},
title = {\textbf{Matching-Vector Families and {LDC}s Over Large Modulo}},
note = {Manuscript},
year = {2013},
url = {./DH13.pdf},
abstract = {{ \textcolor{teal}{We prove an improved upper bound of $O(m^{n/2+ 8.47})$ on the size of Matching-Vector families in $\mathbb{Z}_m^n$ with $m$ an arbitrary composite. This improves the bound $m^{n/2 + O(\log m)}$ 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 $K^{19/18}$ for messages of length $K$.}}}
}
@article{Dvir-survey,
author = {Z. Dvir},
title = {\newline \textbf{Incidence Theorems and Their Applications}},
journal = {Foundations and Trends in Theoretical Computer Science},
volume = {6},
number = {4},
year = {2012},
pages = {257-393},
url = {./Dvir-survey.pdf},
abstract = {{ \textcolor{teal}{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.}} }
}
@article{BDWY12,
author = { B. Barak and Z. Dvir and A. Wigderson and A. Yehudayoff},
title = {\textbf{Fractional {S}ylvester-{G}allai theorems}},
journal = {Proceedings of the National Academy of Sciences},
year = {2012},
note = {(journal version of STOC 11 paepr)},
url = {./BDWYpnas.pdf},
abstract = { \textcolor{teal}{{\it 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.}}}
}
@unpublished{ADSW12,
author = {A. Ai and Z. Dvir and S. Saraf and A. Wigderson},
title = {\textbf{{S}ylvester-{G}allai theorems for approximate collinearity}},
note = {Manuscript},
year = {2012},
url = {./ADSW12.pdf},
abstract = {{ \textcolor{teal}{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 $\epsilon$}.}}
}
@unpublished{DSW12,
author = {Z. Dvir and S. Saraf and A. Wigderson},
title = {\textbf{Improved rank bounds for design matrices and a new proof of {K}elly's theorem.}},
note = {Manuscript},
year = {2012},
url = {DSW12.pdf},
abstract = {{ \textcolor{teal}{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. }}}
}
@unpublished{BDL13,
author = {A. Bhowmick and Z. Dvir and S. Lovett},
title = {\textbf{New Bounds for Matching Vector Families}},
note = {STOC 2013 (to appear)},
year = {2013},
url = {./BDL12.pdf},
abstract = {\textcolor{teal}{We prove new upper bounds for families of vectors in ${\mathbb Z}_m^n$ with restricted dot products mod $m$. Such families, called {\em 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.}}
}
@unpublished{DKL12,
author = {Z. Dvir and J. Koll\'{a}r and S. Lovett},
title = {\textbf{Variety Evasive Sets}},
note = {To appear in Comp. Complex.},
year = {2012},
url = {./DKL12.pdf},
abstract = {\textcolor{teal}{For given $k,n,d$, we give an explicit construction of a large set $S$ in $F^n$, 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).}}
}
@inproceedings{DL12,
author = {Dvir, Z. and Lovett, S.},
title = {\textbf{Subspace evasive sets}},
booktitle = {Proceedings of the 44th symposium on Theory of Computing},
series = {STOC '12},
year = {2012},
isbn = {978-1-4503-1245-5},
location = {New York, New York, USA},
pages = {351--358},
numpages = {8},
url = {./DL12.pdf},
publisher = {ACM},
address = {New York, NY, USA},
abstract = {\textcolor{teal}{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.}}
}
@inproceedings{DRWY12,
author = {Z. Dvir and
A. Rao and
A. Wigderson and
A. Yehudayoff},
title = {\textbf{Restriction access}},
booktitle = {ITCS},
year = {2012},
pages = {19-33},
url = {./DRWY12.pdf},
abstract = {\textcolor{teal}{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.}}
}
@inproceedings{DMPY12,
author = {Dvir, Z. and Malod, G. and Perifel, S. and Yehudayoff, A.},
title = {\textbf{Separating multilinear branching programs and formulas}},
booktitle = {Proceedings of the 44th symposium on Theory of Computing},
series = {STOC '12},
year = {2012},
isbn = {978-1-4503-1245-5},
location = {New York, New York, USA},
pages = {615--624},
numpages = {10},
url = {./DMPY12.pdf},
acmid = {2214034},
publisher = {ACM},
address = {New York, NY, USA},
abstract = {\textcolor{teal}{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 {\em circuits} and formulas.}}
}
@inproceedings{BDSS11,
author = {A. Bhattacharyya and
Z. Dvir and
A. Shpilka and
S. Saraf},
title = {\textbf{Tight Lower Bounds for 2-query LCCs over Finite Fields}},
booktitle = {Proc. of FOCS 2011},
year = {2011},
pages = {638-647},
url = {./BDSS11.pdf},
abstract = {\textcolor{teal}{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.}}
}
@inproceedings{BDWY11,
author = {Barak, B. and Dvir, Z. and Yehudayoff, A. and Wigderson, A.},
title = {\textbf{Rank bounds for design matrices with applications to combinatorial geometry and locally correctable codes}},
booktitle = {Proceedings of the 43rd annual ACM symposium on Theory of computing},
series = {STOC '11},
year = {2011},
isbn = {978-1-4503-0691-1},
location = {San Jose, California, USA},
pages = {519--528},
numpages = {10},
publisher = {ACM},
address = {New York, NY, USA},
url = {./BDWY11.pdf},
abstract = {\textcolor{teal}{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. }}
}
@inproceedings{DGRV11,
author = {Z. Dvir and D. Gutfreund and G. Rothblum and S. Vadhan},
title = {\textbf{On approximating the entropy of polynomial mappings}},
booktitle = {Proceedings of the Second Symposium on Innovations in Computer Science (ICS 2011), Beijing, China, 7-9 January 2011},
year = {2011},
url = {./DGRV11.pdf},
abstract = {\textcolor{teal}{Given a polynomial map $g$ from $F^k$ to $F^n$, where $F$ is a finite field, we study the question of estimating the entropy of $g(U)$ with $U$ distributed uniformly over $F^k$. We give both algorithms and hardness results for some settings of the parameters and discuss its relationship to other problems arising in cryptography. }}
}
@article{DvirGopalanYekhanin10,
author = {Z. Dvir and P. Gopalan and S. Yekhanin},
title = {\textbf{Matching vector codes}},
journal = {SIAM J. Comput.},
volume = {40},
year = {2011},
pages = {1154-1178 },
note = {(Extended abstract appeared in FOCS 2010)},
url = {./DvirGopalanYekhanin10.pdf},
abstract = {\textcolor{teal}{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.}}
}
@article{DvirWigderson10,
author = {Z. Dvir and A. Wigderson},
title = {\textbf{Monotone Expanders: Constructions and Applications}},
year = {2010},
pages = {291-308},
publisher = {Theory of Computing},
journal = {Theory of Computing},
volume = {6},
number = {1},
url = {./DvirWigderson10.pdf},
abstract = {\textcolor{teal}{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.}}
}
@article{Dvir10,
author = {Dvir, Z.},
title = {\textbf{On Matrix Rigidity and Locally Self-correctable Codes}},
journal = {Computational Complexity},
publisher = {Birkhäuser Basel},
issn = {1016-3328},
pages = {367-388},
volume = {20},
number = {2},
year = {2011},
url = {./Dvir10.pdf},
note = {(Extended abstract appeared in CCC 2010)},
abstract = {\textcolor{teal}{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.}}
}
@article{Dvir09b,
author = {Dvir, Z.},
title = {\textbf{From randomness extraction to rotating needles}},
journal = {SIGACT News},
volume = {40},
number = {4},
year = {2009},
issn = {0163-5700},
pages = {46--61},
publisher = {ACM},
address = {New York, NY, USA},
url = {./Dvir09b.pdf},
abstract = {\textcolor{teal}{This survey includes an overview of the finite field Kakeya problem, its solution and the applications to randomness extractors.}}
}
@inproceedings{DKSS09,
author = {Z. Dvir and S. Kopparty and S. Saraf and M. Sudan},
title = {\textbf{Extensions to the Method of Multiplicities, with applications to Kakeya Sets and Mergers}},
booktitle = {Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science (FOCS)},
year = {2009},
isbn = {978-0-7695-3850-1},
pages = {181--190},
publisher = {IEEE Computer Society},
address = {Washington, DC, USA},
url = {./DKSS09.pdf},
abstract = {\textcolor{teal}{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.}}
}
@article{DvirWigderson08,
title = {\textbf{Kakeya Sets, New Mergers, and Old Extractors}},
journal = {SIAM J. on Computing},
year = {2011},
volume = {40},
number = {3},
pages = {778-792},
author = {Z. Dvir and A. Wigderson},
url = {./DvirWigderson08.pdf},
note = {(Extended abstract appeared in FOCS 2008)},
abstract = {\textcolor{teal}{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'. }}
}
@article{Dvir09,
author = {Z. Dvir},
title = {\textbf{On the size of {K}akeya sets in finite fields}},
journal = {J. Amer. Math. Soc.},
volume = {22},
year = {2009},
pages = {1093-1097},
url = {./Dvir09.pdf},
abstract = {\textcolor{teal}{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.}}
}
@article{Dvir08,
year = {2012},
issn = {1016-3328},
journal = {computational complexity},
volume = {21},
issue = {4},
title = {\textbf{Extractors for varieties}},
url = {./Dvir08.pdf},
publisher = {SP Birkhäuser Verlag Basel},
author = {Dvir, Z.},
pages = {515-572},
language = {English},
note = {(Conference version appeared in CCC 09)},
abstract = {\textcolor{teal}{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.}}
}
@article{BDVY13,
author = {A. Bogdanov and Z. Dvir and E. Verbin and A. Yehudayoff},
title = {\textbf{Pseudorandomness for Width 2 Branching Programs}},
year = {2013},
pages = {283--293},
journal = {Theory of Computing},
volume = {9},
number = {7},
url = {./BDVY08.pdf},
abstract = {\textcolor{teal}{A construction of pseudorandom generators for width-2 branching programs using high order Fourier analysis. }}
}
@article{DvirShpilka11,
author = {Z. Dvir and A. Shpilka},
title = {\textbf{Noisy Interpolating Sets for Low-Degree Polynomials}},
year = {2011},
pages = {1-18},
publisher = {Theory of Computing},
journal = {Theory of Computing},
volume = {7},
number = {1},
url = {./DvirShpilka11.pdf},
note = {(Extended abstract appeared in CCC 2008)},
abstract = {\textcolor{teal}{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.}}
}
@article{DvirShpilkaYehudayoff09,
author = {Z. Dvir and A. Shpilka and A. Yehudayoff},
title = {\textbf{Hardness-randomness tradeoffs for bounded depth arithmetic circuits}},
journal = {SIAM J. Comput.},
volume = {39},
number = {4},
year = {2009},
pages = {1279--1293},
url = {./DvirShpilkaYehudayoff09.pdf},
note = {(Extended abstract appeared in STOC '08)},
abstract = {\textcolor{teal}{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.}}
}
@article{DvirShpilka11b,
author = {Z. Dvir and A. Shpilka},
title = {\textbf{Towards dimension expanders over finite fields}},
journal = {Combinatorica},
publisher = {Springer Berlin / Heidelberg},
issn = {0209-9683},
pages = {305-320},
volume = {31},
issue = {3},
url = {./DvirShpilka11b.pdf},
note = {(Extended abstract appeared at CCC '08)},
year = {2011},
abstract = {\textcolor{teal}{We show an explicit construction of a small number of linear maps from $F^n$ to $F^n$, 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).}}
}
@article{DvirGabizonWigderson09,
author = {Z. Dvir and A. Gabizon and A. Wigderson},
title = {\textbf{Extractors And Rank Extractors For Polynomial Sources}},
journal = {Comput. Complex.},
volume = {18},
number = {1},
year = {2009},
issn = {1016-3328},
pages = {1--58},
publisher = {Birkhauser Verlag},
address = {Basel, Switzerland, Switzerland},
url = {./DvirGabizonWigderson07.pdf},
note = {(Extended abstract appeared in FOCS '07)},
abstract = {\textcolor{teal}{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).}}
}
@article{DvirShpilka07,
author = {Z. Dvir and A. Shpilka},
title = {\textbf{An Improved Analysis of Linear Mergers}},
journal = {Comput. Complex.},
volume = {16},
number = {1},
year = {2007},
issn = {1016-3328},
pages = {34--59},
publisher = {Birkhauser Verlag},
address = {Basel, Switzerland, Switzerland},
note = {(Extended abstract appeared in RANDOM '05)},
url = {./DvirShpilka07.pdf},
abstract = {\textcolor{teal}{An improved analysis of the linear mergers proposed by Lu, Reingold, Vadhan and Wigderson using a connection to the finite field Kakeya problem.}}
}
@article{DvirRaz05,
author = {Z. Dvir and R. Raz},
title = {\textbf{Analyzing Linear Mergers}},
journal = {Random Structures and Algorithms},
volume = {32},
number = {3},
pages = {334 -- 345},
year = {2007},
url = {./DvirRaz07.pdf},
abstract = {\textcolor{teal}{An improved analysis of linear mergers obtaining a stronger control over the error.}}
}
@article{DvirShpilka06,
author = {Z. Dvir and A. Shpilka},
title = {\textbf{Locally decodable codes with 2 queries and polynomial identity testing for depth 3 circuits}},
journal = {SIAM J. on Computing},
year = {2006},
pages = {1404-1434},
volume = {36},
number = {5},
note = {(Extended abstract appeared in STOC '05)},
url = {./DvirShpilka06.pdf},
abstract = {\textcolor{teal}{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.