Subhash Khot

Electron. Colloquium Comput. Complex., 2024

Reasonable Bounds for Combinatorial Lines of Length Three.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2024

On Approximability of Satisfiable k-CSPs: VII.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2024

On Approximability of Satisfiable k-CSPs: VI.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2024

Parallel Repetition for 3-Player XOR Games.

[BibT_eX]

[DOI]

CoRR, 2024

2023

Effective Bounds for Restricted $3$-Arithmetic Progressions in $\mathbb{F}_p^n$.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2023

On Approximability of Satisfiable k-CSPs: IV.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2023

On Approximability of Satisfiable k-CSPs: II.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2023

On Approximability of Satisfiable k-CSPs: III.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2023

Parallel Repetition of k-Player Projection Games.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2023

Effective Bounds for Restricted 3-Arithmetic Progressions in Fpn.

[BibT_eX]

[DOI]

CoRR, 2023

On Approximability of Satisfiable k-CSPs: III.

[BibT_eX]

[DOI]

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

On Approximability of Satisfiable k-CSPs: II.

[BibT_eX]

[DOI]

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

Improved Monotonicity Testers via Hypercube Embeddings.

[BibT_eX]

[DOI]

Proceedings of the 14th Innovations in Theoretical Computer Science Conference, 2023

2022

Parallel Repetition for the GHZ Game: Exponential Decay.

[BibT_eX]

[DOI]

Mark Braverman

Electron. Colloquium Comput. Complex., 2022

On Approximability of Satisfiable k-CSPs: I.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2022

Almost Polynomial Factor Inapproximability for Parameterized k-Clique.

[BibT_eX]

[DOI]

Karthik C. S.

Proceedings of the 37th Computational Complexity Conference, 2022

2021

An Invariance Principle for the Multi-slice, with Applications.

[BibT_eX]

[DOI]

Proceedings of the 62nd IEEE Annual Symposium on Foundations of Computer Science, 2021

2020

Theorems of KKL, Friedgut, and Talagrand via Random Restrictions and Log-Sobolev Inequality.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2020

Optimal Inapproximability of Satisfiable k-LIN over Non-Abelian Groups.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2020

2019

Improved 3LIN Hardness via Linear Label Cover.

[BibT_eX]

[DOI]

Prahladh Harsha

Devanathan Thiruvenkatachari

Euiwoong Lee

Electron. Colloquium Comput. Complex., 2019

On Rich $2$-to-$1$ Games.

[BibT_eX]

[DOI]

Mark Braverman

Electron. Colloquium Comput. Complex., 2019

Simultaneous Max-Cut is harder to approximate than Max-Cut.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2019

UG-hardness to NP-hardness by Losing Half.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2019

The Andoni-Krauthgamer-Razenshteyn characterization of sketchable norms fails for sketchable metrics.

[BibT_eX]

[DOI]

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

2018

On Monotonicity Testing and Boolean Isoperimetric-type Theorems.

[BibT_eX]

[DOI]

SIAM J. Comput., 2018

Pseudorandom Sets in Grassmann Graph have Near-Perfect Expansion.

[BibT_eX]

[DOI]

Devanathan Thiruvenkatachari

Electron. Colloquium Comput. Complex., 2018

Small Set Expansion in The Johnson Graph.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2018

Near-optimal approximation algorithm for simultaneous Max-Cut.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

2017

Hardness of Coloring 2-Colorable 12-Uniform Hypergraphs with 2(log n)Ømega(1) Colors.

[BibT_eX]

[DOI]

SIAM J. Comput., 2017

On Non-Optimally Expanding Sets in Grassmann Graphs.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2017

An Improved Dictatorship Test with Perfect Completeness.

[BibT_eX]

[DOI]

Devanathan Thiruvenkatachari

Electron. Colloquium Comput. Complex., 2017

2016

An Õ(n) Queries Adaptive Tester for Unateness.

[BibT_eX]

[DOI]

Igor Shinkar

Electron. Colloquium Comput. Complex., 2016

Approximating CSPs using LP Relaxation.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2016

On Independent Sets, 2-to-2 Games and Grassmann Graphs.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2016

Towards a Proof of the 2-to-1 Games Conjecture?

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2016

An $\widetilde{O}(n)$ Queries Adaptive Tester for Unateness.

[BibT_eX]

[DOI]

Igor Shinkar

CoRR, 2016

Candidate hard unique game.

[BibT_eX]

[DOI]

Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, 2016

Hardness of Approximation.

[BibT_eX]

[DOI]

Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, 2016

Hardness of Bipartite Expansion.

[BibT_eX]

[DOI]

Proceedings of the 24th Annual European Symposium on Algorithms, 2016

2015

The Unique Games Conjecture, Integrality Gap for Cut Problems and Embeddability of Negative-Type Metrics into ℓ1.

[BibT_eX]

[DOI]

J. ACM, 2015

On Hardness of Approximating the Parameterized Clique Problem.

[BibT_eX]

[DOI]

Igor Shinkar

Electron. Colloquium Comput. Complex., 2015

2014

A Simple Deterministic Reduction for the Gap Minimum Distance of Code Problem.

[BibT_eX]

[DOI]

Per Austrin

IEEE Trans. Inf. Theory, 2014

Almost Polynomial Factor Hardness for Closest Vector Problem with Preprocessing.

[BibT_eX]

[DOI]

SIAM J. Comput., 2014

Hardness of Coloring 2-Colorable 12-Uniform Hypergraphs with 2log nΩ(1) Colors.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2014

Candidate Lasserre Integrality Gap For Unique Games.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2014

Hardness of Finding Independent Sets in 2-Colorable and Almost 2-Colorable Hypergraphs.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

Hardness of Coloring 2-Colorable 12-Uniform Hypergraphs with exp(log^{Omega(1)} n) Colors.

[BibT_eX]

[DOI]

Proceedings of the 55th IEEE Annual Symposium on Foundations of Computer Science, 2014

2013

A Two-Prover One-Round Game with Strong Soundness.

[BibT_eX]

[DOI]

Theory Comput., 2013

NP-Hardness of Approximately Solving Linear Equations over Reals.

[BibT_eX]

[DOI]

SIAM J. Comput., 2013

Sharp kernel clustering algorithms and their associated Grothendieck inequalities.

[BibT_eX]

[DOI]

Random Struct. Algorithms, 2013

A Characterization of Approximation Resistance.

[BibT_eX]

[DOI]

Pratik Worah

Electron. Colloquium Comput. Complex., 2013

A Characterization of Strong Approximation Resistance.

[BibT_eX]

[DOI]

Pratik Worah

Electron. Colloquium Comput. Complex., 2013

A characterization of approximation resistance for even k-partite CSPs.

[BibT_eX]

[DOI]

Per Austrin

Proceedings of the Innovations in Theoretical Computer Science, 2013

On Approximation Resistance of Predicates (Invited Talk).

[BibT_eX]

[DOI]

Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2013

2012

The Complexity of Somewhat Approximation Resistant Predicates.

[BibT_eX]

[DOI]

Pratik Worah

Electron. Colloquium Comput. Complex., 2012

Towards An Optimal Query Efficient PCP?

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2012

2log1-ε n hardness for the closest vector problem with preprocessing.

[BibT_eX]

[DOI]

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

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

[BibT_eX]

[DOI]

Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science, 2012

2011

Inapproximability of Vertex Cover and Independent Set in Bounded Degree Graphs.

[BibT_eX]

[DOI]

Per Austrin

Theory Comput., 2011

Combinatorial theorems about embedding trees on the real line.

[BibT_eX]

[DOI]

J. Graph Theory, 2011

On the hardness of learning intersections of two halfspaces.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2011

2log1-έn Hardness for Closest Vector Problem with Preprocessing.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2011

$2^{\log^{1-\eps} n}$ Hardness for Closest Vector Problem with Preprocessing

[BibT_eX]

[DOI]

CoRR, 2011

Grothendieck-type inequalities in combinatorial optimization

[BibT_eX]

[DOI]

CoRR, 2011

Hardness of Approximating the Closest Vector Problem with Pre-Processing.

[BibT_eX]

[DOI]

Comput. Complex., 2011

2010

Inapproximability Results for Computational Problems on Lattices.

[BibT_eX]

[DOI]

Proceedings of the LLL Algorithm - Survey and Applications, 2010

Hardness of Reconstructing Multivariate Polynomials over Finite Fields.

[BibT_eX]

[DOI]

Parikshit Gopalan

SIAM J. Comput., 2010

Hardness of Approximately Solving Linear Equations Over Reals.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2010

NP-Hardness of Approximately Solving Linear Equations Over Reals.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2010

Limits of Approximation Algorithms: PCPs and Unique Games (DIMACS Tutorial Lecture Notes)

[BibT_eX]

[DOI]

CoRR, 2010

SDP Gaps for 2-to-1 and Other Label-Cover Variants.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 37th International Colloquium, 2010

Inapproximability of Hypergraph Vertex Cover and Applications to Scheduling Problems.

[BibT_eX]

[DOI]

Nikhil Bansal

Proceedings of the Automata, Languages and Programming, 37th International Colloquium, 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

On the Unique Games Conjecture (Invited Survey).

[BibT_eX]

[DOI]

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

Approximate Lasserre Integrality Gap for Unique Games.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2010

2009

SDP Gaps and UGC-hardness for Max-Cut-Gain.

[BibT_eX]

[DOI]

Ryan O'Donnell

Theory Comput., 2009

On Earthmover Distance, Metric Labeling, and 0-Extension.

[BibT_eX]

[DOI]

SIAM J. Comput., 2009

On Agnostic Learning of Parities, Monomials, and Halfspaces.

[BibT_eX]

[DOI]

Vitaly Feldman

Parikshit Gopalan

SIAM J. Comput., 2009

SDP Integrality Gaps with Local ell_1-Embeddability.

[BibT_eX]

[DOI]

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

Optimal Long Code Test with One Free Bit.

[BibT_eX]

[DOI]

Nikhil Bansal

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

2008

Linear Equations Modulo 2 and the L1 Diameter of Convex Bodies.

[BibT_eX]

[DOI]

SIAM J. Comput., 2008

Vertex cover might be hard to approximate to within 2-epsilon.

[BibT_eX]

[DOI]

Oded Regev

J. Comput. Syst. Sci., 2008

Inapproximability Results for Combinatorial Auctions with Submodular Utility Functions.

[BibT_eX]

[DOI]

Algorithmica, 2008

On hardness of learning intersection of two halfspaces.

[BibT_eX]

[DOI]

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

Unique games on expanding constraint graphs are easy: extended abstract.

[BibT_eX]

[DOI]

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

Hardness of Minimizing and Learning DNF Expressions.

[BibT_eX]

[DOI]

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

Approximate Kernel Clustering.

[BibT_eX]

[DOI]

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

Minimizing Wide Range Regret with Time Selection Functions.

[BibT_eX]

[DOI]

Proceedings of the 21st Annual Conference on Learning Theory, 2008

2007

Optimal Inapproximability Results for MAX-CUT and Other 2-Variable CSPs?.

[BibT_eX]

[DOI]

SIAM J. Comput., 2007

Improved lower bounds on the randomized complexity of graph properties.

[BibT_eX]

[DOI]

Random Struct. Algorithms, 2007

Linear Equations Modulo 2 and the L1 Diameter of Convex Bodies.

[BibT_eX]

[DOI]

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

Hardness of Embedding Metric Spaces of Equal Size.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2007

Approximation Algorithms for the Max-Min Allocation Problem.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2007

2006

Ruling Out PTAS for Graph Min-Bisection, Dense k-Subgraph, and Bipartite Clique.

[BibT_eX]

[DOI]

SIAM J. Comput., 2006

Hardness of approximating the Shortest Vector Problem in high lp norms.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2006

New Results for Learning Noisy Parities and Halfspaces.

[BibT_eX]

[DOI]

Vitaly Feldman

Parikshit Gopalan

Electron. Colloquium Comput. Complex., 2006

Integrality gaps for sparsest cut and minimum linear arrangement problems.

[BibT_eX]

[DOI]

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

Better Inapproximability Results for MaxClique, Chromatic Number and Min-3Lin-Deletion.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 33rd International Colloquium, 2006

SDP gaps and UGC-hardness for MAXCUTGAIN.

[BibT_eX]

[DOI]

Ryan O'Donnell

Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), 2006

A 3-Query Non-Adaptive PCP with Perfect Completeness.

[BibT_eX]

[DOI]

Proceedings of the 21st Annual IEEE Conference on Computational Complexity (CCC 2006), 2006

2005

Query Efficient PCPs with Perfect Completeness.

[BibT_eX]

[DOI]

Johan Håstad

Theory Comput., 2005

Guest column: inapproximability results via Long Code based PCPs.

[BibT_eX]

[DOI]

SIGACT News, 2005

A New Multilayered PCP and the Hardness of Hypergraph Vertex Cover.

[BibT_eX]

[DOI]

SIAM J. Comput., 2005

Hardness of approximating the shortest vector problem in lattices.

[BibT_eX]

[DOI]

J. ACM, 2005

Nonembeddability theorems via Fourier analysis.

[BibT_eX]

[DOI]

Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005), 2005

On the Unique Games Conjecture.

[BibT_eX]

[DOI]

Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005), 2005

Hardness of Max 3SAT with No Mixed Clauses.

[BibT_eX]

[DOI]

Venkatesan Guruswami

Proceedings of the 20th Annual IEEE Conference on Computational Complexity (CCC 2005), 2005

2004

Cell-probe lower bounds for the partial match problem.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2004

A new PCP outer verifier with applications to homogeneous linear equations and max-bisection.

[BibT_eX]

[DOI]

Jonas Holmerin

Proceedings of the 36th Annual ACM Symposium on Theory of Computing, 2004

Ruling Out PTAS for Graph Min-Bisection, Densest Subgraph and Bipartite Clique.

[BibT_eX]

[DOI]

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

2003

Fitting algebraic curves to noisy data.

[BibT_eX]

[DOI]

Sanjeev Arora

J. Comput. Syst. Sci., 2003

Hardness of Approximating the Shortest Vector Problem in High Lp Norms.

[BibT_eX]

[DOI]

Proceedings of the 44th Symposium on Foundations of Computer Science (FOCS 2003), 2003

Vertex Cover Might be Hard to Approximate to within 2-\varepsilon.

[BibT_eX]

[DOI]

Oded Regev

Proceedings of the 18th Annual IEEE Conference on Computational Complexity (Complexity 2003), 2003

A Strong Inapproximability Gap for a Generalization of Minimum Bisection.

[BibT_eX]

[DOI]

Jonas Holmerin

Proceedings of the 18th Annual IEEE Conference on Computational Complexity (Complexity 2003), 2003

Near-Optimal Lower Bounds on the Multi-Party Communication Complexity of Set Disjointness.

[BibT_eX]

[DOI]

Xiaodong Sun

Proceedings of the 18th Annual IEEE Conference on Computational Complexity (Complexity 2003), 2003

2002

Parameterized complexity of finding subgraphs with hereditary properties.

[BibT_eX]

[DOI]

Venkatesh Raman

Theor. Comput. Sci., 2002

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

[BibT_eX]

[DOI]

Irit Dinur

Venkatesan Guruswami

Electron. Colloquium Comput. Complex., 2002

On the power of unique 2-prover 1-round games.

[BibT_eX]

[DOI]

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

Hardness results for approximate hypergraph coloring.

[BibT_eX]

[DOI]

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

Hardness Results for Coloring 3 -Colorable 3 -Uniform Hypergraphs.

[BibT_eX]

[DOI]

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

2001

Evasiveness of Subgraph Containment and Related Properties.

[BibT_eX]

[DOI]

Yaoyun Shi

SIAM J. Comput., 2001

Improved Inaproximability Results for MaxClique, Chromatic Number and Approximate Graph Coloring.

[BibT_eX]

[DOI]