Zeev Dvir

Ben Lund

Discret. Comput. Geom., March, 2024

2022

Guest Editors' Foreword to the CCC 2020 Special Issue.

[BibT_eX]

[DOI]

Avishay Tal

Theory Comput., 2022

Linear Hashing with ℓ<sub>∞</sub> guarantees and two-sided Kakeya bounds.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2022

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

[BibT_eX]

[DOI]

Proceedings of the 63rd IEEE Annual Symposium on Foundations of Computer Science, 2022

2021

Proof of the Kakeya set conjecture over rings of integers modulo square-free N.

[BibT_eX]

[DOI]

Comb. Theory, 2021

2020

A Sauer-Shelah-Perles Lemma for Lattices.

[BibT_eX]

[DOI]

Electron. J. Comb., 2020

2019

Matrix Rigidity and the Croot-Lev-Pach Lemma.

[BibT_eX]

[DOI]

Benjamin L. Edelman

Theory Comput., 2019

Static data structure lower bounds imply rigidity.

[BibT_eX]

[DOI]

Alexander Golovnev

Omri Weinstein

Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019

Spanoids - An Abstraction of Spanning Structures, and a Barrier for LCCs.

[BibT_eX]

[DOI]

Proceedings of the 10th Innovations in Theoretical Computer Science Conference, 2019

Fourier and Circulant Matrices Are Not Rigid.

[BibT_eX]

[DOI]

Allen Liu

Proceedings of the 34th Computational Complexity Conference, 2019

2018

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

[BibT_eX]

[DOI]

CoRR, 2018

A Sauer-Shelah-Perles Lemma for Sumsets.

[BibT_eX]

[DOI]

Shay Moran

Electron. J. Comb., 2018

2017

Superquadratic Lower Bound for 3-Query Locally Correctable Codes over the Reals.

[BibT_eX]

[DOI]

Theory Comput., 2017

Outlaw Distributions and Locally Decodable Codes.

[BibT_eX]

[DOI]

Jop Briët

Proceedings of the 8th Innovations in Theoretical Computer Science Conference, 2017

On the Number of Ordinary Lines Determined by Sets in Complex Space.

[BibT_eX]

[DOI]

Proceedings of the 33rd International Symposium on Computational Geometry, 2017

2016

2-Server PIR with Subpolynomial Communication.

[BibT_eX]

[DOI]

J. ACM, 2016

Rank bounds for design matrices with block entries and geometric applications.

[BibT_eX]

[DOI]

CoRR, 2016

Tight lower bounds for linear 2-query LCCs over finite fields.

[BibT_eX]

[DOI]

Comb., 2016

Special issue "Computational Complexity Conference 2015" Guest Editors' Foreword.

[BibT_eX]

[DOI]

David Zuckerman

Comput. Complex., 2016

Affine extractors over large fields with exponential error.

[BibT_eX]

[DOI]

Jean Bourgain

Ethan Leeman

Comput. Complex., 2016

2015

A Quantitative Variant of the Multi-colored Motzkin-Rabin Theorem.

[BibT_eX]

[DOI]

Christian Tessier-Lavigne

Discret. Comput. Geom., 2015

2-Server PIR with Sub-Polynomial Communication.

[BibT_eX]

[DOI]

Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, 2015

Sylvester-Gallai for Arrangements of Subspaces.

[BibT_eX]

[DOI]

Guangda Hu

Proceedings of the 31st International Symposium on Computational Geometry, 2015

On the Number of Rich Lines in Truly High Dimensional Sets.

[BibT_eX]

[DOI]

Proceedings of the 31st International Symposium on Computational Geometry, 2015

2014

Factors of Sparse Polynomials are Sparse.

[BibT_eX]

[DOI]

Rafael Oliveira

Electron. Colloquium Comput. Complex., 2014

Lower Bounds for Approximate LDC.

[BibT_eX]

[DOI]

CoRR, 2014

Variety Evasive Sets.

[BibT_eX]

[DOI]

János Kollár

Comput. Complex., 2014

Breaking the quadratic barrier for 3-LCC's over the reals.

[BibT_eX]

[DOI]

Proceedings of the Symposium on Theory of Computing, 2014

Testing Equivalence of Polynomials under Shifts.

[BibT_eX]

[DOI]

Rafael Oliveira

Proceedings of the Automata, Languages, and Programming - 41st International Colloquium, 2014

Lower Bounds for Approximate LDCs.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages, and Programming - 41st International Colloquium, 2014

2013

Breaking the quadratic barrier for 3-LCCs over the Reals.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2013

New bounds for matching vector families.

[BibT_eX]

[DOI]

Abhishek Bhowmick

Proceedings of the Symposium on Theory of Computing Conference, 2013

Matching-Vector Families and LDCs over Large Modulo.

[BibT_eX]

[DOI]

Guangda Hu

Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2013

2012

Incidence Theorems and Their Applications.

[BibT_eX]

[DOI]

Found. Trends Theor. Comput. Sci., 2012

Improved rank bounds for design matrices and a new proof of Kelly's theorem.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2012

New Lower Bounds for Matching Vector Codes.

[BibT_eX]

[DOI]

Abhishek Bhowmick

Electron. Colloquium Comput. Complex., 2012

Sylvester-Gallai type theorems for approximate collinearity.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2012

Separating multilinear branching programs and formulas.

[BibT_eX]

[DOI]

Proceedings of the 44th Symposium on Theory of Computing Conference, 2012

Subspace evasive sets.

[BibT_eX]

[DOI]

Proceedings of the 44th Symposium on Theory of Computing Conference, 2012

Restriction access.

[BibT_eX]

[DOI]

Proceedings of the Innovations in Theoretical Computer Science 2012, 2012

2011

Rank bounds for design matrices with applications toc ombinatorial geometry and locally correctable codes.

[BibT_eX]

[DOI]

Proceedings of the 43rd ACM Symposium on Theory of Computing, 2011

On Approximating the Entropy of Polynomial Mappings.

[BibT_eX]

[DOI]

Proceedings of the Innovations in Computer Science, 2011

Tight Lower Bounds for 2-query LCCs over Finite Fields.

[BibT_eX]

[DOI]

Proceedings of the IEEE 52nd Annual Symposium on Foundations of Computer Science, 2011

2010

Rank Bounds for Design Matrices with Applications to Combinatorial Geometry and Locally Correctable Codes.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2010

Matching Vector Codes.

[BibT_eX]

[DOI]

Parikshit Gopalan

Sergey Yekhanin

Proceedings of the 51th Annual IEEE Symposium on Foundations of Computer Science, 2010

On Matrix Rigidity and Locally Self-Correctable Codes.

[BibT_eX]

[DOI]

Proceedings of the 25th Annual IEEE Conference on Computational Complexity, 2010

2009

Guest column: from randomness extraction to rotating needles.

[BibT_eX]

[DOI]

SIGACT News, 2009

Monotone expanders - constructions and applications.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2009

From Randomness Extraction to Rotating Needles.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2009

Pseudorandomness for Width 2 Branching Programs.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2009

Extensions to the Method of Multiplicities, with Applications to Kakeya Sets and Mergers.

[BibT_eX]

[DOI]

Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science, 2009

Extractors for Varieties.

[BibT_eX]

[DOI]

Proceedings of the 24th Annual IEEE Conference on Computational Complexity, 2009

2008

Deterministic Extractors for Algebraic Sources.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2008

Hardness-randomness tradeoffs for bounded depth arithmetic circuits.

[BibT_eX]

[DOI]

Amir Yehudayoff

Proceedings of the 40th Annual ACM Symposium on Theory of Computing, 2008

Kakeya Sets, New Mergers and Old Extractors.

[BibT_eX]

[DOI]

Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, 2008

Towards Dimension Expanders over Finite Fields.

[BibT_eX]

[DOI]

Proceedings of the 23rd Annual IEEE Conference on Computational Complexity, 2008

Noisy Interpolating Sets for Low Degree Polynomials.

[BibT_eX]

[DOI]

Proceedings of the 23rd Annual IEEE Conference on Computational Complexity, 2008

2007

Locally Decodable Codes with Two Queries and Polynomial Identity Testing for Depth 3 Circuits.

[BibT_eX]

[DOI]

SIAM J. Comput., 2007

An Improved Analysis of Linear Mergers.

[BibT_eX]

[DOI]

Comput. Complex., 2007

Extractors and Rank Extractors for Polynomial Sources.

[BibT_eX]

[DOI]

Ariel Gabizon

Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, 2007

2005

Analyzing Linear Mergers

[BibT_eX]

[DOI]

Ran Raz

Electron. Colloquium Comput. Complex., 2005

Locally decodable codes with 2 queries and polynomial identity testing for depth 3 circuits.

[BibT_eX]

[DOI]

Proceedings of the 37th Annual ACM Symposium on Theory of Computing, 2005

An Improved Analysis of Mergers.

[BibT_eX]

[DOI]