Irit Dinur

Siqi Liu

Rachel Yun Zhang

Proceedings of the 40th Computational Complexity Conference, 2025

2024

Bipartite Unique Neighbour Expanders via Ramanujan Graphs.

[BibT_eX]

[DOI]

Ron Asherov

Entropy, April, 2024

Sparse juntas on the biased hypercube.

[BibT_eX]

[DOI]

TheoretiCS, 2024

Expansion of higher-dimensional cubical complexes with application to quantum locally testable codes.

[BibT_eX]

[DOI]

Ting-Chun Lin

Thomas Vidick

CoRR, 2024

Agreement Theorems for High Dimensional Expanders in the Low Acceptance Regime: The Role of Covers.

[BibT_eX]

[DOI]

Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024

Swap Cosystolic Expansion.

[BibT_eX]

[DOI]

Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024

Expansion of High-Dimensional Cubical Complexes: with Application to Quantum Locally Testable Codes.

[BibT_eX]

[DOI]

Ting-Chun Lin

Thomas Vidick

Proceedings of the 65th IEEE Annual Symposium on Foundations of Computer Science, 2024

Low Acceptance Agreement Tests via Bounded-Degree Symplectic HDXs.

[BibT_eX]

[DOI]

Alexander Lubotzky

Proceedings of the 65th IEEE Annual Symposium on Foundations of Computer Science, 2024

Coboundary and Cosystolic Expansion Without Dependence on Dimension or Degree.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2024

2023

Agreement theorems for high dimensional expanders in the small soundness regime: the role of covers.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2023

The linear time encoding scheme fails to encode.

[BibT_eX]

[DOI]

Shiri Sivan

CoRR, 2023

Good Quantum LDPC Codes with Linear Time Decoders.

[BibT_eX]

[DOI]

Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023

2022

Good Locally Testable Codes.

[BibT_eX]

[DOI]

CoRR, 2022

Locally testable codes with constant rate, distance, and locality.

[BibT_eX]

[DOI]

Proceedings of the STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20, 2022

Expanders in Higher Dimensions (Invited Talk).

[BibT_eX]

[DOI]

Proceedings of the 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2022

A Characterization of Multiclass Learnability.

[BibT_eX]

[DOI]

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

2021

Explicit SoS Lower Bounds from High-Dimensional Expanders.

[BibT_eX]

[DOI]

Proceedings of the 12th Innovations in Theoretical Computer Science Conference, 2021

2020

Explicit and structured sum of squares lower bounds from high dimensional expanders.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2020

Locally testable codes via high-dimensional expanders.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2020

2019

Special Section on the Fifty-Seventh Annual IEEE Symposium on Foundations of Computer Science (FOCS 2016).

[BibT_eX]

[DOI]

Swastik Kopparty

SIAM J. Comput., 2019

Near Coverings and Cosystolic Expansion - an example of topological property testing.

[BibT_eX]

[DOI]

Roy Meshulam

Electron. Colloquium Comput. Complex., 2019

Testing tensor products.

[BibT_eX]

[DOI]

Konstantin Golubev

CoRR, 2019

List Decoding with Double Samplers.

[BibT_eX]

[DOI]

Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

Analyzing Boolean functions on the biased hypercube via higher-dimensional agreement tests: [Extended abstract].

[BibT_eX]

[DOI]

Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

From Local to Robust Testing via Agreement Testing.

[BibT_eX]

[DOI]

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

Every Set in P Is Strongly Testable Under a Suitable Encoding.

[BibT_eX]

[DOI]

Oded Goldreich

Tom Gur

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

Agreement Testing Theorems on Layered Set Systems.

[BibT_eX]

[DOI]

Proceedings of the 60th IEEE Annual Symposium on Foundations of Computer Science, 2019

Direct Sum Testing: The General Case.

[BibT_eX]

[DOI]

Konstantin Golubev

Proceedings of the Approximation, 2019

2018

From Local to Robust Testing via Agreement Testing.

[BibT_eX]

[DOI]

Tali Kaufman

Noga Ron-Zewi

Electron. Colloquium Comput. Complex., 2018

Boolean functions on high-dimensional expanders.

[BibT_eX]

[DOI]

CoRR, 2018

On non-optimally expanding sets in Grassmann graphs.

[BibT_eX]

[DOI]

Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018

Towards a proof of the 2-to-1 games conjecture?

[BibT_eX]

[DOI]

Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018

ETH-Hardness of Approximating 2-CSPs and Directed Steiner Network.

[BibT_eX]

[DOI]

Pasin Manurangsi

Proceedings of the 9th Innovations in Theoretical Computer Science Conference, 2018

Boolean Function Analysis on High-Dimensional Expanders.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2018

2017

Agreement tests on graphs and hypergraphs.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2017

Low degree almost Boolean functions are sparse juntas.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2017

Multiplayer Parallel Repetition for Expanding Games.

[BibT_eX]

[DOI]

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

Cube vs. Cube Low Degree Test.

[BibT_eX]

[DOI]

Amey Bhangale

Inbal Livni Navon

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

High Dimensional Expanders Imply Agreement Expanders.

[BibT_eX]

[DOI]

Tali Kaufman

Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science, 2017

Exponentially Small Soundness for the Direct Product Z-Test.

[BibT_eX]

[DOI]

Inbal Livni Navon

Proceedings of the 32nd Computational Complexity Conference, 2017

2016

Multiplayer parallel repetition for expander games.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2016

Mildly exponential reduction from gap 3SAT to polynomial-gap label-cover.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2016

Toward the KRW Composition Conjecture: Cubic Formula Lower Bounds via Communication Complexity.

[BibT_eX]

[DOI]

Proceedings of the 31st Conference on Computational Complexity, 2016

2015

Polynomially Low Error PCPs with polyloglogn Queries via Modular Composition.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2015

Polynomially Low Error PCPs with polyloglog n Queries via Modular Composition.

[BibT_eX]

[DOI]

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

Derandomized Graph Product Results Using the Low Degree Long Code.

[BibT_eX]

[DOI]

Proceedings of the 32nd International Symposium on Theoretical Aspects of Computer Science, 2015

The Computational Benefit of Correlated Instances.

[BibT_eX]

[DOI]

Shafi Goldwasser

Huijia Lin

Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science, 2015

Direct Sum Testing.

[BibT_eX]

[DOI]

Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science, 2015

2014

Analytical approach to parallel repetition.

[BibT_eX]

[DOI]

David Steurer

Proceedings of the Symposium on Theory of Computing, 2014

A Parallel Repetition Theorem for Entangled Projection Games.

[BibT_eX]

[DOI]

David Steurer

Thomas Vidick

Proceedings of the IEEE 29th Conference on Computational Complexity, 2014

Direct Product Testing.

[BibT_eX]

[DOI]

David Steurer

Proceedings of the IEEE 29th Conference on Computational Complexity, 2014

2013

Special Issue "Conference on Computational Complexity 2012" Guest editors' foreword.

[BibT_eX]

[DOI]

Boaz Barak

Comput. Complex., 2013

Clustering in the Boolean Hypercube in a List Decoding Regime.

[BibT_eX]

[DOI]

Elazar Goldenberg

Proceedings of the Automata, Languages, and Programming - 40th International Colloquium, 2013

PCPs via Low-Degree Long Code and Hardness for Constrained Hypergraph Coloring.

[BibT_eX]

[DOI]

Venkatesan Guruswami

Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science, 2013

Covering CSPs.

[BibT_eX]

[DOI]

Gillat Kol

Proceedings of the 28th Conference on Computational Complexity, 2013

2011

Derandomized Parallel Repetition via Structured PCPs.

[BibT_eX]

[DOI]

Comput. Complex., 2011

PCP Characterizations of NP: Toward a Polynomially-Small Error-Probability.

[BibT_eX]

[DOI]

Comput. Complex., 2011

Dense Locally Testable Codes Cannot Have Constant Rate and Distance.

[BibT_eX]

[DOI]

Tali Kaufman

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

2010

Composition of Low-Error 2-Query PCPs Using Decodable PCPs.

[BibT_eX]

[DOI]

Proceedings of the Property Testing - Current Research and Surveys, 2010

Hardness of Finding Independent Sets in Almost 3-Colorable Graphs.

[BibT_eX]

[DOI]

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

Derandomized Parallel Repetition of Structured PCPs.

[BibT_eX]

[DOI]

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

On the Conditional Hardness of Coloring a 4-Colorable Graph with Super-Constant Number of Colors.

[BibT_eX]

[DOI]

Igor Shinkar

Proceedings of the Approximation, 2010

The Structure of Winning Strategies in Parallel Repetition Games.

[BibT_eX]

[DOI]

Elazar Goldenberg

Proceedings of the Approximation, 2010

2009

Intersecting Families are Essentially Contained in Juntas.

[BibT_eX]

[DOI]

Ehud Friedgut

Comb. Probab. Comput., 2009

Composition of Low-Error 2-Query PCPs Using Decodable PCPs.

[BibT_eX]

[DOI]

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

2008

PCPs with small soundness error.

[BibT_eX]

[DOI]

SIGACT News, 2008

Special Issue on Foundations of Computer Science.

[BibT_eX]

Éva Tardos

SIAM J. Comput., 2008

Decodability of group homomorphisms beyond the johnson bound.

[BibT_eX]

[DOI]

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

Locally Testing Direct Product in the Low Error Range.

[BibT_eX]

[DOI]

Elazar Goldenberg

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

2006

Proof of an Intersection Theorem via Graph Homomorphisms.

[BibT_eX]

[DOI]

Ehud Friedgut

Electron. J. Comb., 2006

Conditional hardness for approximate coloring.

[BibT_eX]

[DOI]

Elchanan Mossel

Oded Regev

Proceedings of the 38th Annual ACM Symposium on Theory of Computing, 2006

On the fourier tails of bounded functions over the discrete cube.

[BibT_eX]

[DOI]

Proceedings of the 38th Annual ACM Symposium on Theory of Computing, 2006

The PCP theorem by gap amplification.

[BibT_eX]

[DOI]

Proceedings of the 38th Annual ACM Symposium on Theory of Computing, 2006

Robust Local Testability of Tensor Products of LDPC Codes.

[BibT_eX]

[DOI]

Madhu Sudan

Avi Wigderson

Proceedings of the Approximation, 2006

2004

Assignment Testers: Towards a Combinatorial Proof of the PCP-Theorem.

[BibT_eX]

[DOI]

Omer Reingold

Proceedings of the 45th Symposium on Foundations of Computer Science, 2004

2003

Approximating CVP to Within Almost-Polynomial Factors is NP-Hard.

[BibT_eX]

[DOI]

Comb., 2003

A new multilayered PCP and the hardness of hypergraph vertex cover.

[BibT_eX]

[DOI]

Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 2003

Revealing information while preserving privacy.

[BibT_eX]

[DOI]

Kobbi Nissim

Proceedings of the Twenty-Second ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 2003

2002

Approximating SVP<sub>infinity</sub> to within almost-polynomial factors is NP-hard.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2002

Vertex Cover on k-Uniform Hypergraphs is Hard to Approximate within Factor (k-3-epsilon)

[BibT_eX]

[DOI]

Venkatesan Guruswami

Subhash Khot

Electron. Colloquium Comput. Complex., 2002

The importance of being biased.

[BibT_eX]

[DOI]

Proceedings of the Proceedings on 34th Annual ACM Symposium on Theory of Computing, 2002

The Hardness of 3 - Uniform Hypergraph Coloring.

[BibT_eX]

[DOI]

Oded Regev

Clifford D. Smyth

Proceedings of the 43rd Symposium on Foundations of Computer Science, 2002

2000

Approximating SVP<sub>infty</sub> to within Almost-Polynomial Factors Is NP-Hard.

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Complexity, 4th Italian Conference, 2000

1999

On the Hardness of Approximating Label Cover

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 1999

PCP Characterizations of NP: Towards a Polynomially-Small Error-Probability.

[BibT_eX]

[DOI]

Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, 1999

1998

Approximating CVP to Within Almost Polynomial Factor is NP-Hard

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 1998

Approximating-CVP to Within Almost-Polynomial Factors is NP-Hard.

[BibT_eX]

[DOI]