Zeev Dvir

Publications

  1. The Sylvester–Gallai dimension of graphs

    Z. Dvir. Manuscript. 2026.

    arXiv

  2. Rank-metric separation in irreducible representations of finite groups

    Z. Dvir. Linear Algebra and its Applications 748 (2026), 1–14.

    arXiv

  3. Tensor rank and dimension expanders

    Z. Dvir. Manuscript. 2025.

    arXiv

  4. Linear Hashing with ℓ∞ guarantees and two-sided Kakeya bounds

    M. Dhar and Z. Dvir. TheoretiCS, April 3, 2024, Volume 3 (preliminary version in FOCS 22').

    Open Journal link

  5. Furstenberg sets in finite fields: Explaining and improving the Ellenberg-Erman proof

    M. Dhar, Z. Dvir and B. Lund. Discrete Comput Geom 71, 327–357 (2024).

    arXiv

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

  7. Simple proofs for Furstenberg sets over finite fields

    M. Dhar, Z. Dvir and B. Lund. Discrete Analysis 2021:22, 16 pp.

    Open journal

  8. Fourier and Circulant Matrices are Not Rigid

    Z. Dvir and A. Liu. Theory of Computation, Volume 16 (2020) Article 20 pp. 1-48 (CCC 2019 Special Issue).

    arXiv

  9. Spanoids - an abstraction of spanning structures, and a barrier for LCCs

    Z. Dvir, S. Gopi, Y. Gu, A. Wigderson. SIAM Journal on Computing Vol. 49, Iss. 3. 2020.

    arXiv

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

  11. Matrix rigidity and the Croot-Lev-Pach lemma

    Z. Dvir and B. Edelman. Theory of Computing, Volume 15 pp. 1-7 [Note]. 2019.

    arXiv

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

  13. A Sauer-Shelah-Perles Lemma for Sumsets

    Z. Dvir and S. Moran. Electronic Journal of Combinatorics 25(4). 2018.

    arXiv

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

  15. Outlaw distributions and locally decodable codes

    J. Briet and Z. Dvir and S. Gopi. ITCS 2017.

    pdf

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

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

  18. Affine extractors over large fields with exponential error

    J. Bourgain, Z. Dvir, and E. Leeman. comput. complex. (2016) 25: 921.

    pdf

  19. On the number of rich lines in truly high dimensional sets

    Z. Dvir and S. Gopi. Proc. of 31st International Symposium on Computational Geometry (SoCG 2015). Vol 34 pp. 584--598.

    pdf

  20. Sylvester-Gallai for arrangements of subspaces

    Z. Dvir and G. Hu. Proc. of 31st International Symposium on Computational Geometry (SoCG 2015). Vol 34 pp. 29--43.

    pdf

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

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

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

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

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

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

  27. Variety Evasive Sets

    Z. Dvir, J. Kollár, and S. Lovett. computational complexity, 23(4):509-529, 2014.

    pdf

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

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

  30. Pseudorandomness for Width 2 Branching Programs

    A. Bogdanov, Z. Dvir, E. Verbin, and A. Yehudayoff. Theory of Computing, 9(7):283-293, 2013.

    pdf

  31. Incidence Theorems and Their Applications

    Z. Dvir. Foundations and Trends in Theoretical Computer Science, 6(4):257-393, 2012.

    pdf

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

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

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

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

  36. Extractors for varieties

    Z. Dvir. computational complexity, 21:515-572, 2012. (Conference version appeared in CCC 09).

    pdf

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

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

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

  40. Matching vector codes

    Z. Dvir, P. Gopalan, and S. Yekhanin. SIAM J. Comput., 40:1154-1178, 2011. (Extended abstract appeared in FOCS 2010).

    pdf

  41. On Matrix Rigidity and Locally Self-correctable Codes

    Z. Dvir. Computational Complexity, 20(2):367-388, 2011.

    pdf

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

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

  44. Towards dimension expanders over finite fields

    Z. Dvir and A. Shpilka. Combinatorica, 31:305-320, 2011. (Extended abstract appeared at CCC '08).

    pdf

  45. Monotone Expanders: Constructions and Applications

    Z. Dvir and A. Wigderson. Theory of Computing, 6(1):291-308, 2010.

    pdf

  46. From randomness extraction to rotating needles

    Z. Dvir. SIGACT News, 40(4):46-61, 2009.

    pdf

  47. On the size of Kakeya sets in finite fields

    Z. Dvir. J. Amer. Math. Soc., 22:1093-1097, 2009.

    pdf

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

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

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

  51. Analyzing Linear Mergers

    Z. Dvir and R. Raz. Random Structures and Algorithms, 32(3):334-345, 2007.

    pdf

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