Linear Hashing with ℓ∞ guarantees and two-sided Kakeya bounds
, M. Dhar and Z. Dvir
To appear in FOCS 22'. 2022. [ arXiv ]
Proof of the Kakeya set conjecture over rings of integers modulo square-free N , M. Dhar and Z. Dvir
Combinatorial Theory 1(0). 2021. [ Open journals are the best ]
Simple proofs for Furstenberg sets over finite fields, M. Dhar, Z. Dvir and B. Lund
Discrete Analysis 2021:22, 16 pp. [ Open journal ]
Furstenberg sets in finite fields: Explaining and improving the Ellenberg-Erman proof, M. Dhar, Z. Dvir and B. Lund
To appear in DCG. 2019. [ arXiv ]
Fourier and Circulant Matrices are Not Rigid, Z. Dvir and A. Liu
In 34th Computational Complexity Conference (CCC 2019), volume 137 of LIPIcs, 1–17:23, 2019 [ arXiv ]
Static Data Structure Lower Bounds Imply Rigidity, Z. Dvir and A. Golovnev and O. Weinstein
STOC 2019 Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing Pages 967-978 . 2019. [ arXiv ]
Spanoids - an abstraction of spanning structures, and a barrier for LCCs, Z. Dvir, S. Gopi, Y. Gu, A. Wigderson
ITCS 2019. [ arXiv ]
A Sauer-Shelah-Perles Lemma for Sumsets, Z. Dvir and S. Moran
Electronic Journal of Combinatorics 25(4). 2018. [ arXiv ]
Matrix rigidity and the Croot-Lev-Pach lemma, Z. Dvir and B. Edelman
Theory of Computing, Volume 15 pp.1-7 [Note]. 2019 [ arXiv ]
On the number of ordinary lines determined by sets in complex space, A. Basit, Z. Dvir, S. Saraf and C. Wolf
Discrete & Computational Geometry, 61(4):778–808, 2019. [ arXiv ]
Rank bounds for design matrices with block entries and geometric applications, Z. Dvir and A. Garg and R. Oliveira and J. Solymosi.
Discrete Analysis 2018:5, 24 pp. [ support open journals ]
Outlaw distributions and locally decodable codes, J. Briet and Z. Dvir and S. Gopi.
ITCS 2017. [ pdf ]
On the number of rich lines in truly high dimensional sets, Z. Dvir and S. Gopi. 2015.
Proc. of 31st International Symposium on Computational Geometry (SoCG 2015). Vol 34 pp. 584--598. [ pdf ]
Sylvester-Gallai for arrangements of subspaces, Z. Dvir and G. Hu. 2015.
Proc. of 31st International Symposium on Computational Geometry (SoCG 2015). Vol 34 pp. 29--43. [ pdf ]
2-Server PIR with sub polynomial communication, Z. Dvir and S. Gopi.
JACM Volume 63 Issue 4, November 2016 (Extended abstract appeared in STOC 2015). [ pdf ]
A quantitative variant of the multi-colored Motzkin-Rabin theorem. Z. Dvir and C. Tessier-Lavigne.
Discrete and Computational Geometry, 53(1):38-47, 2015. [ pdf ]
Lower Bounds for Approximate LDCs. J. Briet, Z. Dvir, G. Hu, and S. Saraf.
In Automata, Languages, and Programming (ICALP 2014), volume 8572 of pdf ]
Affine extractors over large fields with exponential error, J. Bourgain, Z. Dvir, and E. Leeman.
comput. complex. (2016) 25: 921 [ pdf ]
Testing Equivalence of Polynomials under Shifts. Z. Dvir, R.M de Oliveira, and A. Shpilka.
In Automata, Languages, and Programming (ICALP 2014), volume 8572 of pdf ]
Superquadratic Lower Bound for 3-Query Locally Correctable Codes over the Reals. Z. Dvir, S. Saraf, and A. Wigderson.
Theory of Computing, 13(11):1–36, 2017. [ pdf ]
Matching-Vector Families and LDCs Over Large Modulo. Z. Dvir and G. Hu.
In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (RANDOM-APPROX), volume 8096, pages 513-526. Springer Berlin Heidelberg, 2013. [ pdf ]
Incidence Theorems and Their Applications. Z. Dvir.
Foundations and Trends in Theoretical Computer Science, 6(4):257-393, 2012. [ pdf ]
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). [ pdf ]
Sylvester-Gallai theorems for approximate collinearity, A. Ai, Z. Dvir, S. Saraf, and A. Wigderson.
Forum of Mathematics, Sigma, 2, E3. doi:10.1017/fms.2014.1. [ pdf ]
Improved rank bounds for design matrices and a new proof of Kelly's theorem., Z. Dvir, S. Saraf, and A. Wigderson.
Forum of Mathematics, Sigma, 2, E4. doi:10.1017/fms.2014.2 [ pdf ]
New Bounds for Matching Vector Families. A. Bhowmick, Z. Dvir, and S. Lovett.
SIAM Journal on Computing (Extended abstract appeared in STOC '13), 43(5):1654-1683, 2014. [ pdf ]
Variety Evasive Sets. Z. Dvir, J. Kollár, and S. Lovett.
computational complexity, 23(4):509-529, 2014. [ pdf ]
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. [ pdf ]
Restriction access. Z. Dvir, A. Rao, A. Wigderson, and A. Yehudayoff.
In Proceedings of the 3rd Innovations in Theoretical Computer Science Conference (ITCS), pages 19-33. ACM, 2012. [ pdf ]
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. [ pdf ]
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. [ pdf ]
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. [ pdf ]
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. [ pdf ]
Matching vector codes. Z. Dvir, P. Gopalan, and S. Yekhanin.
SIAM J. Comput., 40:1154-1178, 2011. (Extended abstract appeared in FOCS 2010). [ pdf ]
Monotone Expanders: Constructions and Applications. Z. Dvir and A. Wigderson.
Theory of Computing, 6(1):291-308, 2010. [ pdf ]
On Matrix Rigidity and Locally Self-correctable Codes. Z. Dvir.
Computational Complexity, 20(2):367-388, 2011. [ pdf ]
From randomness extraction to rotating needles. Z. Dvir.
SIGACT News, 40(4):46-61, 2009. [ pdf ]
Extensions to the Method of Multiplicities, with Applications to Kakeya Sets and Mergers. Z. Dvir, S. Kopparty, S. Saraf, and M. Sudan.
SIAM Journal on Computing, 42(6):2305-2328, 2013. (Extended abstract appeared in FOCS 2009). [ pdf ]
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). [ pdf ]
On the size of Kakeya sets in finite fields. Z. Dvir.
J. Amer. Math. Soc., 22:1093-1097, 2009. [ pdf ]
Extractors for varieties. Z. Dvir.
computational complexity, 21:515-572, 2012. (Conference version appeared in CCC 09). [ pdf ]
Pseudorandomness for Width 2 Branching Programs. A. Bogdanov, Z. Dvir, E. Verbin, and A. Yehudayoff.
Theory of Computing, 9(7):283-293, 2013. [ pdf ]
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). [ pdf ]
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). [ pdf ]
Towards dimension expanders over finite fields. Z. Dvir and A. Shpilka.
Combinatorica, 31:305-320, 2011. (Extended abstract appeared at CCC '08). [ pdf ]
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). [ pdf ]
An Improved Analysis of Linear Mergers. Z. Dvir and A. Shpilka.
Comput. Complex., 16(1):34-59, 2007. (Extended abstract appeared in RANDOM '05). [ pdf ]
Analyzing Linear Mergers. Z. Dvir and R. Raz.
Random Structures and Algorithms, 32(3):334 - 345, 2007. [ pdf ]
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). [ pdf ]
To appear in FOCS 22'. 2022. [ arXiv ]
Proof of the Kakeya set conjecture over rings of integers modulo square-free N , M. Dhar and Z. Dvir
Combinatorial Theory 1(0). 2021. [ Open journals are the best ]
Simple proofs for Furstenberg sets over finite fields, M. Dhar, Z. Dvir and B. Lund
Discrete Analysis 2021:22, 16 pp. [ Open journal ]
Furstenberg sets in finite fields: Explaining and improving the Ellenberg-Erman proof, M. Dhar, Z. Dvir and B. Lund
To appear in DCG. 2019. [ arXiv ]
Fourier and Circulant Matrices are Not Rigid, Z. Dvir and A. Liu
In 34th Computational Complexity Conference (CCC 2019), volume 137 of LIPIcs, 1–17:23, 2019 [ arXiv ]
Static Data Structure Lower Bounds Imply Rigidity, Z. Dvir and A. Golovnev and O. Weinstein
STOC 2019 Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing Pages 967-978 . 2019. [ arXiv ]
Spanoids - an abstraction of spanning structures, and a barrier for LCCs, Z. Dvir, S. Gopi, Y. Gu, A. Wigderson
ITCS 2019. [ arXiv ]
A Sauer-Shelah-Perles Lemma for Sumsets, Z. Dvir and S. Moran
Electronic Journal of Combinatorics 25(4). 2018. [ arXiv ]
Matrix rigidity and the Croot-Lev-Pach lemma, Z. Dvir and B. Edelman
Theory of Computing, Volume 15 pp.1-7 [Note]. 2019 [ arXiv ]
On the number of ordinary lines determined by sets in complex space, A. Basit, Z. Dvir, S. Saraf and C. Wolf
Discrete & Computational Geometry, 61(4):778–808, 2019. [ arXiv ]
Rank bounds for design matrices with block entries and geometric applications, Z. Dvir and A. Garg and R. Oliveira and J. Solymosi.
Discrete Analysis 2018:5, 24 pp. [ support open journals ]
Outlaw distributions and locally decodable codes, J. Briet and Z. Dvir and S. Gopi.
ITCS 2017. [ pdf ]
On the number of rich lines in truly high dimensional sets, Z. Dvir and S. Gopi. 2015.
Proc. of 31st International Symposium on Computational Geometry (SoCG 2015). Vol 34 pp. 584--598. [ pdf ]
Sylvester-Gallai for arrangements of subspaces, Z. Dvir and G. Hu. 2015.
Proc. of 31st International Symposium on Computational Geometry (SoCG 2015). Vol 34 pp. 29--43. [ pdf ]
2-Server PIR with sub polynomial communication, Z. Dvir and S. Gopi.
JACM Volume 63 Issue 4, November 2016 (Extended abstract appeared in STOC 2015). [ pdf ]
A quantitative variant of the multi-colored Motzkin-Rabin theorem. Z. Dvir and C. Tessier-Lavigne.
Discrete and Computational Geometry, 53(1):38-47, 2015. [ pdf ]
Lower Bounds for Approximate LDCs. J. Briet, Z. Dvir, G. Hu, and S. Saraf.
In Automata, Languages, and Programming (ICALP 2014), volume 8572 of pdf ]
Affine extractors over large fields with exponential error, J. Bourgain, Z. Dvir, and E. Leeman.
comput. complex. (2016) 25: 921 [ pdf ]
Testing Equivalence of Polynomials under Shifts. Z. Dvir, R.M de Oliveira, and A. Shpilka.
In Automata, Languages, and Programming (ICALP 2014), volume 8572 of pdf ]
Superquadratic Lower Bound for 3-Query Locally Correctable Codes over the Reals. Z. Dvir, S. Saraf, and A. Wigderson.
Theory of Computing, 13(11):1–36, 2017. [ pdf ]
Matching-Vector Families and LDCs Over Large Modulo. Z. Dvir and G. Hu.
In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (RANDOM-APPROX), volume 8096, pages 513-526. Springer Berlin Heidelberg, 2013. [ pdf ]
Incidence Theorems and Their Applications. Z. Dvir.
Foundations and Trends in Theoretical Computer Science, 6(4):257-393, 2012. [ pdf ]
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). [ pdf ]
Sylvester-Gallai theorems for approximate collinearity, A. Ai, Z. Dvir, S. Saraf, and A. Wigderson.
Forum of Mathematics, Sigma, 2, E3. doi:10.1017/fms.2014.1. [ pdf ]
Improved rank bounds for design matrices and a new proof of Kelly's theorem., Z. Dvir, S. Saraf, and A. Wigderson.
Forum of Mathematics, Sigma, 2, E4. doi:10.1017/fms.2014.2 [ pdf ]
New Bounds for Matching Vector Families. A. Bhowmick, Z. Dvir, and S. Lovett.
SIAM Journal on Computing (Extended abstract appeared in STOC '13), 43(5):1654-1683, 2014. [ pdf ]
Variety Evasive Sets. Z. Dvir, J. Kollár, and S. Lovett.
computational complexity, 23(4):509-529, 2014. [ pdf ]
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. [ pdf ]
Restriction access. Z. Dvir, A. Rao, A. Wigderson, and A. Yehudayoff.
In Proceedings of the 3rd Innovations in Theoretical Computer Science Conference (ITCS), pages 19-33. ACM, 2012. [ pdf ]
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. [ pdf ]
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. [ pdf ]
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. [ pdf ]
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. [ pdf ]
Matching vector codes. Z. Dvir, P. Gopalan, and S. Yekhanin.
SIAM J. Comput., 40:1154-1178, 2011. (Extended abstract appeared in FOCS 2010). [ pdf ]
Monotone Expanders: Constructions and Applications. Z. Dvir and A. Wigderson.
Theory of Computing, 6(1):291-308, 2010. [ pdf ]
On Matrix Rigidity and Locally Self-correctable Codes. Z. Dvir.
Computational Complexity, 20(2):367-388, 2011. [ pdf ]
From randomness extraction to rotating needles. Z. Dvir.
SIGACT News, 40(4):46-61, 2009. [ pdf ]
Extensions to the Method of Multiplicities, with Applications to Kakeya Sets and Mergers. Z. Dvir, S. Kopparty, S. Saraf, and M. Sudan.
SIAM Journal on Computing, 42(6):2305-2328, 2013. (Extended abstract appeared in FOCS 2009). [ pdf ]
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). [ pdf ]
On the size of Kakeya sets in finite fields. Z. Dvir.
J. Amer. Math. Soc., 22:1093-1097, 2009. [ pdf ]
Extractors for varieties. Z. Dvir.
computational complexity, 21:515-572, 2012. (Conference version appeared in CCC 09). [ pdf ]
Pseudorandomness for Width 2 Branching Programs. A. Bogdanov, Z. Dvir, E. Verbin, and A. Yehudayoff.
Theory of Computing, 9(7):283-293, 2013. [ pdf ]
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). [ pdf ]
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). [ pdf ]
Towards dimension expanders over finite fields. Z. Dvir and A. Shpilka.
Combinatorica, 31:305-320, 2011. (Extended abstract appeared at CCC '08). [ pdf ]
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). [ pdf ]
An Improved Analysis of Linear Mergers. Z. Dvir and A. Shpilka.
Comput. Complex., 16(1):34-59, 2007. (Extended abstract appeared in RANDOM '05). [ pdf ]
Analyzing Linear Mergers. Z. Dvir and R. Raz.
Random Structures and Algorithms, 32(3):334 - 345, 2007. [ pdf ]
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). [ pdf ]