Zeev Dvir

List of research outcomes

This list is not complete and representing at the moment only items from zbMATH Open and arXiv. We are working on additional sources - please check back here soon!

Publication	Date of Publication	Type
Linear hashing with $\ell_\infty$ guarantees and two-sided Kakeya bounds TheoretiCS	2024-07-03	Paper
Furstenberg sets in finite fields: explaining and improving the Ellenberg-Erman proof Discrete & Computational Geometry	2024-02-09	Paper
Proof of the Kakeya set conjecture over rings of integers modulo square-free $N$ Combinatorial Theory	2022-11-16	Paper
Fourier and circulant matrices are not rigid	2022-07-27	Paper
Spanoids - An Abstraction of Spanning Structures, and a Barrier for LCCs	2022-07-18	Paper
Simple proofs for Furstenberg sets over finite fields discrete Analysis	2022-02-10	Paper
Fourier and circulant matrices are not rigid Theory of Computing	2021-04-01	Paper
A Sauer-Shelah-Perles lemma for lattices The Electronic Journal of Combinatorics	2020-11-05	Paper
Spanoids -- an abstraction of spanning structures, and a barrier for LCCs SIAM Journal on Computing	2020-05-28	Paper
Static data structure lower bounds imply rigidity Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing	2020-01-30	Paper
Matrix rigidity and the Croot-Lev-Pach lemma Theory of Computing	2019-12-05	Paper
Outlaw distributions and locally decodable codes Theory of Computing	2019-12-05	Paper
Simple proofs for Furstenberg sets over finite fields	2019-09-06	Paper
On the number of ordinary lines determined by sets in complex space Discrete & Computational Geometry	2019-05-21	Paper
A Sauer-Shelah-Perles lemma for sumsets The Electronic Journal of Combinatorics	2018-11-22	Paper
On the number of ordinary lines determined by sets in complex space	2018-08-13	Paper
2-server PIR with subpolynomial communication Journal of the ACM	2018-08-02	Paper
Outlaw distributions and locally decodable codes	2018-05-03	Paper
Superquadratic lower bound for 3-query locally correctable codes over the reals Theory of Computing	2017-11-14	Paper
On the number of rich lines in truly high dimensional sets	2017-10-10	Paper
Sylvester-Gallai for arrangements of subspaces	2017-10-10	Paper
Tight lower bounds for linear $2$-query LCCs over finite fields. With an appendix by Sergey Yekhanin. Combinatorica	2017-03-31	Paper
Sylvester-Gallai for arrangements of subspaces Discrete & Computational Geometry	2016-12-20	Paper
Affine extractors over large fields with exponential error Computational Complexity	2016-11-30	Paper
Restriction access Proceedings of the 3rd Innovations in Theoretical Computer Science Conference	2016-10-07	Paper
2-server PIR with sub-polynomial communication Proceedings of the forty-seventh annual ACM symposium on Theory of Computing	2015-08-21	Paper
Breaking the quadratic barrier for 3-LCC's over the reals Proceedings of the forty-sixth annual ACM symposium on Theory of computing	2015-06-26	Paper
A quantitative variant of the multi-colored Motzkin-Rabin theorem Discrete & Computational Geometry	2015-02-19	Paper
New bounds for matching vector families SIAM Journal on Computing	2015-02-09	Paper
Variety evasive sets Computational Complexity	2014-11-26	Paper
Improved rank bounds for design matrices and a new proof of Kelly's theorem Forum of Mathematics, Sigma	2014-09-01	Paper
Sylvester-Gallai type theorems for approximate collinearity Forum of Mathematics, Sigma	2014-09-01	Paper
New bounds for matching vector families Proceedings of the forty-eighth annual ACM symposium on Theory of Computing	2014-08-07	Paper
Tight Lower Bounds for 2-query LCCs over Finite Fields 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science	2014-07-30	Paper
Extensions to the Method of Multiplicities, with Applications to Kakeya Sets and Mergers 2009 50th Annual IEEE Symposium on Foundations of Computer Science	2014-07-25	Paper
Fractional Sylvester–Gallai theorems Proceedings of the National Academy of Sciences	2014-07-25	Paper
Lower bounds for approximate LDCs Automata, Languages, and Programming	2014-07-01	Paper
Testing equivalence of polynomials under shifts Automata, Languages, and Programming	2014-07-01	Paper
Rank bounds for design matrices with applications to combinatorial geometry and locally correctable codes Proceedings of the forty-third annual ACM symposium on Theory of computing	2014-06-05	Paper
Separating multilinear branching programs and formulas Proceedings of the forty-fourth annual ACM symposium on Theory of computing	2014-05-13	Paper
Subspace evasive sets Proceedings of the forty-fourth annual ACM symposium on Theory of computing	2014-05-13	Paper
Factors of Sparse Polynomials are Sparse	2014-04-18	Paper
Extensions to the method of multiplicities, with applications to Kakeya sets and mergers SIAM Journal on Computing	2014-04-11	Paper
Incidence theorems and their applications Foundations and Trends in Theoretical Computer Science	2014-01-08	Paper
Matching-vector families and LDCs over large modulo Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques	2013-10-04	Paper
Extractors for varieties Computational Complexity	2012-12-27	Paper
Towards dimension expanders over finite fields Combinatorica	2011-12-20	Paper
On matrix rigidity and locally self-correctable codes Computational Complexity	2011-11-08	Paper
Matching vector codes SIAM Journal on Computing	2011-11-07	Paper
Kakeya sets, new mergers, and old extractors SIAM Journal on Computing	2011-10-18	Paper
Monotone expanders: constructions and applications Theory of Computing	2011-05-24	Paper
Noisy interpolating sets for low-degree polynomials Theory of Computing	2011-05-24	Paper
Extractors and rank extractors for polynomial sources Computational Complexity	2011-02-18	Paper
On the size of Kakeya sets in finite fields Journal of the American Mathematical Society	2010-11-19	Paper
Hardness-randomness tradeoffs for bounded depth arithmetic circuits SIAM Journal on Computing	2010-09-06	Paper
Locally decodable codes with 2 queries and polynomial identity testing for depth 3 circuits Proceedings of the thirty-seventh annual ACM symposium on Theory of computing	2010-08-16	Paper
scientific article; zbMATH DE number 5485588 (Why is no real title available?)	2009-01-05	Paper
Analyzing linear mergers Random Structures & Algorithms	2008-06-05	Paper
An improved analysis of linear mergers Computational Complexity	2008-02-22	Paper
Locally Decodable Codes with Two Queries and Polynomial Identity Testing for Depth 3 Circuits SIAM Journal on Computing	2007-10-22	Paper
Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques Lecture Notes in Computer Science	2006-07-07	Paper
Linear Hashing with $\ell_\infty$ guarantees and two-sided Kakeya bounds	N/A	Paper

Research outcomes over time

This page was built for person: Zeev Dvir

Publication	Date of Publication	Type
Linear hashing with \(\ell_\infty\) guarantees and two-sided Kakeya bounds TheoretiCS	2024-07-03	Paper
Furstenberg sets in finite fields: explaining and improving the Ellenberg-Erman proof Discrete & Computational Geometry	2024-02-09	Paper
Proof of the Kakeya set conjecture over rings of integers modulo square-free \(N\) Combinatorial Theory	2022-11-16	Paper
Fourier and circulant matrices are not rigid	2022-07-27	Paper
Spanoids - An Abstraction of Spanning Structures, and a Barrier for LCCs	2022-07-18	Paper
Simple proofs for Furstenberg sets over finite fields discrete Analysis	2022-02-10	Paper
Fourier and circulant matrices are not rigid Theory of Computing	2021-04-01	Paper
A Sauer-Shelah-Perles lemma for lattices The Electronic Journal of Combinatorics	2020-11-05	Paper
Spanoids -- an abstraction of spanning structures, and a barrier for LCCs SIAM Journal on Computing	2020-05-28	Paper
Static data structure lower bounds imply rigidity Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing	2020-01-30	Paper
Matrix rigidity and the Croot-Lev-Pach lemma Theory of Computing	2019-12-05	Paper
Outlaw distributions and locally decodable codes Theory of Computing	2019-12-05	Paper
Simple proofs for Furstenberg sets over finite fields	2019-09-06	Paper
On the number of ordinary lines determined by sets in complex space Discrete & Computational Geometry	2019-05-21	Paper
A Sauer-Shelah-Perles lemma for sumsets The Electronic Journal of Combinatorics	2018-11-22	Paper
On the number of ordinary lines determined by sets in complex space	2018-08-13	Paper
2-server PIR with subpolynomial communication Journal of the ACM	2018-08-02	Paper
Outlaw distributions and locally decodable codes	2018-05-03	Paper
Superquadratic lower bound for 3-query locally correctable codes over the reals Theory of Computing	2017-11-14	Paper
On the number of rich lines in truly high dimensional sets	2017-10-10	Paper
Sylvester-Gallai for arrangements of subspaces	2017-10-10	Paper
Tight lower bounds for linear \(2\)-query LCCs over finite fields. With an appendix by Sergey Yekhanin. Combinatorica	2017-03-31	Paper
Sylvester-Gallai for arrangements of subspaces Discrete & Computational Geometry	2016-12-20	Paper
Affine extractors over large fields with exponential error Computational Complexity	2016-11-30	Paper
Restriction access Proceedings of the 3rd Innovations in Theoretical Computer Science Conference	2016-10-07	Paper
2-server PIR with sub-polynomial communication Proceedings of the forty-seventh annual ACM symposium on Theory of Computing	2015-08-21	Paper
Breaking the quadratic barrier for 3-LCC's over the reals Proceedings of the forty-sixth annual ACM symposium on Theory of computing	2015-06-26	Paper
A quantitative variant of the multi-colored Motzkin-Rabin theorem Discrete & Computational Geometry	2015-02-19	Paper
New bounds for matching vector families SIAM Journal on Computing	2015-02-09	Paper
Variety evasive sets Computational Complexity	2014-11-26	Paper
Improved rank bounds for design matrices and a new proof of Kelly's theorem Forum of Mathematics, Sigma	2014-09-01	Paper
Sylvester-Gallai type theorems for approximate collinearity Forum of Mathematics, Sigma	2014-09-01	Paper
New bounds for matching vector families Proceedings of the forty-eighth annual ACM symposium on Theory of Computing	2014-08-07	Paper
Tight Lower Bounds for 2-query LCCs over Finite Fields 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science	2014-07-30	Paper
Extensions to the Method of Multiplicities, with Applications to Kakeya Sets and Mergers 2009 50th Annual IEEE Symposium on Foundations of Computer Science	2014-07-25	Paper
Fractional Sylvester–Gallai theorems Proceedings of the National Academy of Sciences	2014-07-25	Paper
Lower bounds for approximate LDCs Automata, Languages, and Programming	2014-07-01	Paper
Testing equivalence of polynomials under shifts Automata, Languages, and Programming	2014-07-01	Paper
Rank bounds for design matrices with applications to combinatorial geometry and locally correctable codes Proceedings of the forty-third annual ACM symposium on Theory of computing	2014-06-05	Paper
Separating multilinear branching programs and formulas Proceedings of the forty-fourth annual ACM symposium on Theory of computing	2014-05-13	Paper
Subspace evasive sets Proceedings of the forty-fourth annual ACM symposium on Theory of computing	2014-05-13	Paper
Factors of Sparse Polynomials are Sparse	2014-04-18	Paper
Extensions to the method of multiplicities, with applications to Kakeya sets and mergers SIAM Journal on Computing	2014-04-11	Paper
Incidence theorems and their applications Foundations and Trends in Theoretical Computer Science	2014-01-08	Paper
Matching-vector families and LDCs over large modulo Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques	2013-10-04	Paper
Extractors for varieties Computational Complexity	2012-12-27	Paper
Towards dimension expanders over finite fields Combinatorica	2011-12-20	Paper
On matrix rigidity and locally self-correctable codes Computational Complexity	2011-11-08	Paper
Matching vector codes SIAM Journal on Computing	2011-11-07	Paper
Kakeya sets, new mergers, and old extractors SIAM Journal on Computing	2011-10-18	Paper
Monotone expanders: constructions and applications Theory of Computing	2011-05-24	Paper
Noisy interpolating sets for low-degree polynomials Theory of Computing	2011-05-24	Paper
Extractors and rank extractors for polynomial sources Computational Complexity	2011-02-18	Paper
On the size of Kakeya sets in finite fields Journal of the American Mathematical Society	2010-11-19	Paper
Hardness-randomness tradeoffs for bounded depth arithmetic circuits SIAM Journal on Computing	2010-09-06	Paper
Locally decodable codes with 2 queries and polynomial identity testing for depth 3 circuits Proceedings of the thirty-seventh annual ACM symposium on Theory of computing	2010-08-16	Paper
scientific article; zbMATH DE number 5485588 (Why is no real title available?)	2009-01-05	Paper
Analyzing linear mergers Random Structures & Algorithms	2008-06-05	Paper
An improved analysis of linear mergers Computational Complexity	2008-02-22	Paper
Locally Decodable Codes with Two Queries and Polynomial Identity Testing for Depth 3 Circuits SIAM Journal on Computing	2007-10-22	Paper
Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques Lecture Notes in Computer Science	2006-07-07	Paper
Linear Hashing with $\ell_\infty$ guarantees and two-sided Kakeya bounds	N/A	Paper