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]

Manik Dhar

Electron. Colloquium Comput. Complex., 2022

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

[BibT_eX]

[DOI]

Manik Dhar

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

2020

Fourier and Circulant Matrices are Not Rigid.

[BibT_eX]

[DOI]

Allen Liu

Theory Comput., 2020

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

[BibT_eX]

[DOI]

SIAM J. Comput., 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

Outlaw Distributions and Locally Decodable Codes.

[BibT_eX]

[DOI]

Jop Briët

Theory Comput., 2019

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

[BibT_eX]

[DOI]

Discret. Comput. Geom., 2019

2018

Static Data Structure Lower Bounds Imply Rigidity.

[BibT_eX]

[DOI]

Alexander Golovnev

Omri Weinstein

Electron. Colloquium Comput. Complex., 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

2016

2-Server PIR with Subpolynomial Communication.

[BibT_eX]

[DOI]

J. ACM, 2016

Sylvester-Gallai for Arrangements of Subspaces.

[BibT_eX]

[DOI]

Guangda Hu

Discret. Comput. Geom., 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

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

New Bounds for Matching Vector Families.

[BibT_eX]

[DOI]

Abhishek Bhowmick

SIAM J. Comput., 2014

Testing Equivalence of Polynomials under Shifts.

[BibT_eX]

[DOI]

Rafael Oliveira

Electron. Colloquium Comput. Complex., 2014

Factors of Sparse Polynomials are Sparse.

[BibT_eX]

[DOI]

Rafael Oliveira

Electron. Colloquium Comput. Complex., 2014

2-Server PIR with sub-polynomial communication.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2014

Lower Bounds for Approximate LDCs.

[BibT_eX]

[DOI]

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

2013

Pseudorandomness for Width-2 Branching Programs.

[BibT_eX]

[DOI]

Theory Comput., 2013

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

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2013

Matching-Vector Families and LDCs Over Large Modulo.

[BibT_eX]

[DOI]

Guangda Hu

Electron. Colloquium Comput. Complex., 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

Extractors for varieties.

[BibT_eX]

[DOI]

Comput. Complex., 2012

2011

Noisy Interpolating Sets for Low-Degree Polynomials.

[BibT_eX]

[DOI]

Theory Comput., 2011

Restriction Access.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2011

Separating multilinear branching programs and formulas.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2011

Subspace Evasive Sets.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2011

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

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2011

Towards dimension expanders over finite fields.

[BibT_eX]

[DOI]

Comb., 2011

On Matrix Rigidity and Locally Self-correctable Codes.

[BibT_eX]

[DOI]

Comput. Complex., 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

2010

Monotone Expanders: Constructions and Applications.

[BibT_eX]

[DOI]

Theory Comput., 2010

Matching Vector Codes.

[BibT_eX]

[DOI]

Parikshit Gopalan

Sergey Yekhanin

Electron. Colloquium Comput. Complex., 2010

On Approximating the Entropy of Polynomial Mappings.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2010

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

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2010

2009

Guest column: from randomness extraction to rotating needles.

[BibT_eX]

[DOI]

SIGACT News, 2009

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

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2009

From Randomness Extraction to Rotating Needles.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2009

Extractors And Rank Extractors For Polynomial Sources.

[BibT_eX]

[DOI]

Ariel Gabizon

Comput. Complex., 2009

2008

Kakeya sets, new mergers and old extractors.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2008

Deterministic Extractors for Algebraic Sources.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2008

2007

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

[BibT_eX]

[DOI]

SIAM J. Comput., 2007

Hardness-Randomness Tradeoffs for Bounded Depth Arithmetic Circuits.

[BibT_eX]

[DOI]

Amir Yehudayoff

Electron. Colloquium Comput. Complex., 2007

An Improved Analysis of Linear Mergers.

[BibT_eX]

[DOI]

Comput. Complex., 2007

2005

An Improved Analysis of Mergers

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2005

Locally Decodable Codes with 2 queries and Polynomial Identity Testing for depth 3 circuits

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2005

Analyzing Linear Mergers

[BibT_eX]

[DOI]