Subhash Khot

Comput. Complex., December, 2025

On Approximability of Satisfiable k-CSPs: V.

[BibT_eX]

[DOI]

Proceedings of the 57th Annual ACM Symposium on Theory of Computing, 2025

Parallel Repetition for 3-Player XOR Games.

[BibT_eX]

[DOI]

Proceedings of the 57th Annual ACM Symposium on Theory of Computing, 2025

Maximum Span Hypothesis: A Potentially Weaker Assumption than Gap-ETH for Parameterized Complexity.

[BibT_eX]

[DOI]

Karthik C. S.

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

Biased Linearity Testing in the 1% Regime.

[BibT_eX]

[DOI]

Kunal Mittal

Proceedings of the 40th Computational Complexity Conference, 2025

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

On Approximability of Satisfiable k-CSPs: VII.

[BibT_eX]

[DOI]

CoRR, 2024

On Approximability of Satisfiable k-CSPs: VI.

[BibT_eX]

[DOI]

CoRR, 2024

On Approximability of Satisfiable k-CSPs: IV.

[BibT_eX]

[DOI]

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

Parallel Repetition of k-Player Projection Games.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 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: II.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2023

On Approximability of Satisfiable k-CSPs: III.

[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

Parallel Repetition for the GHZ Game: Exponential Decay.

[BibT_eX]

[DOI]

Mark Braverman

Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

2022

On approximability of satisfiable k-CSPs: I.

[BibT_eX]

[DOI]

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

Almost Polynomial Factor Inapproximability for Parameterized k-Clique.

[BibT_eX]

[DOI]

Karthik C. S.

Proceedings of the 37th Computational Complexity Conference, 2022

2021

Optimal inapproximability of satisfiable k-LIN over non-abelian groups.

[BibT_eX]

[DOI]

Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021

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

[BibT_eX]

[DOI]

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

On Rich 2-to-1 Games.

[BibT_eX]

[DOI]

Mark Braverman

Proceedings of the 12th Innovations in Theoretical Computer Science Conference, 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

Simultaneous Max-Cut Is Harder to Approximate Than Max-Cut.

[BibT_eX]

[DOI]

Proceedings of the 35th Computational Complexity Conference, 2020

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

UG-Hardness to NP-Hardness by Losing Half.

[BibT_eX]

[DOI]

Proceedings of the 34th Computational Complexity Conference, 2019

Improved 3LIN Hardness via Linear Label Cover.

[BibT_eX]

[DOI]

Prahladh Harsha

Devanathan Thiruvenkatachari

Euiwoong Lee

Proceedings of the Approximation, 2019

2018

Small Set Expansion in The Johnson Graph.

[BibT_eX]

[DOI]

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

Near-optimal approximation algorithm for simultaneous Max-Cut.

[BibT_eX]

[DOI]

Devanathan Thiruvenkatachari

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

Pseudorandom Sets in Grassmann Graph Have Near-Perfect Expansion.

[BibT_eX]

[DOI]

Proceedings of the 59th IEEE Annual Symposium on Foundations of Computer Science, 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 independent sets, 2-to-2 games, and Grassmann graphs.

[BibT_eX]

[DOI]

Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017

An Improved Dictatorship Test with Perfect Completeness.

[BibT_eX]

[DOI]

Devanathan Thiruvenkatachari

Proceedings of the 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2017

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

On Hardness of Approximating the Parameterized Clique Problem.

[BibT_eX]

[DOI]

Igor Shinkar

Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science, 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

An ~O(n) Queries Adaptive Tester for Unateness.

[BibT_eX]

[DOI]

Igor Shinkar

Proceedings of the Approximation, 2016

2015

Approximating CSPs Using LP Relaxation.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages, and Programming - 42nd International Colloquium, 2015

On Monotonicity Testing and Boolean Isoperimetric Type Theorems.

[BibT_eX]

[DOI]

Proceedings of the IEEE 56th Annual Symposium on Foundations of Computer Science, 2015

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

A characterization of strong approximation resistance.

[BibT_eX]

[DOI]

Pratik Worah

Proceedings of the Symposium on Theory of Computing, 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

The Complexity of Somewhat Approximation Resistant Predicates.

[BibT_eX]

[DOI]

Pratik Worah

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

NP-Hardness of Approximately Solving Linear Equations over Reals.

[BibT_eX]

[DOI]

SIAM J. Comput., 2013

A Characterization of Approximation Resistance.

[BibT_eX]

[DOI]

Pratik Worah

Electron. Colloquium Comput. Complex., 2013

Towards an optimal query efficient PCP?

[BibT_eX]

[DOI]

Proceedings of the Innovations in Theoretical Computer Science, 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

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

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

NP-hardness of approximately solving linear equations over reals.

[BibT_eX]

[DOI]

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

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

[BibT_eX]

[DOI]

Per Austrin

Proceedings of the Automata, Languages and Programming - 38th International Colloquium, 2011

A Two Prover One Round Game with Strong Soundness.

[BibT_eX]

[DOI]

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

2010

Inapproximability Results for Computational Problems on Lattices.

[BibT_eX]

[DOI]

Proceedings of the LLL Algorithm - Survey and Applications, 2010

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

Sharp Kernel Clustering Algorithms and Their Associated Grothendieck Inequalities.

[BibT_eX]

[DOI]

Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, 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 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

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

[BibT_eX]

[DOI]

Per Austrin

Proceedings of the 24th Annual IEEE Conference on Computational Complexity, 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

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

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, 2007

Hardness of Reconstructing Multivariate Polynomials over Finite Fields.

[BibT_eX]

[DOI]

Parikshit Gopalan

Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, 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

On earthmover distance, metric labeling, and 0-extension.

[BibT_eX]

[DOI]

Proceedings of the 38th Annual ACM Symposium on Theory of Computing, 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, 2006

New Results for Learning Noisy Parities and Halfspaces.

[BibT_eX]

[DOI]

Vitaly Feldman

Parikshit Gopalan

Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, 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

Guest column: inapproximability results via Long Code based PCPs.

[BibT_eX]

[DOI]

SIGACT News, 2005

Inapproximability Results for Combinatorial Auctions with Submodular Utility Functions.

[BibT_eX]

[DOI]

Proceedings of the Internet and Network Economics, First International Workshop, 2005

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

[BibT_eX]

[DOI]

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

Nonembeddability theorems via Fourier analysis.

[BibT_eX]

[DOI]

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

On the Unique Games Conjecture.

[BibT_eX]

[DOI]

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

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

[BibT_eX]

[DOI]

Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, 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

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

Optimal Inapproximability Results for Max-Cut and Other 2-Variable CSPs?

[BibT_eX]

[DOI]

Proceedings of the 45th Symposium on Foundations of Computer Science, 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, 2004

Hardness of Approximating the Shortest Vector Problem in Lattices.

[BibT_eX]

[DOI]

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

2003

Cell-probe lower bounds for the partial match problem.

[BibT_eX]

[DOI]

Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 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

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

[BibT_eX]

[DOI]

Proceedings of the 44th Symposium on Foundations of Computer Science, 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

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

Hardness results for approximate hypergraph coloring.

[BibT_eX]

[DOI]

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

Fitting algebraic curves to noisy data.

[BibT_eX]

[DOI]

Sanjeev Arora

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, 2002

On the Power of Unique 2-Prover 1-Round Games.

[BibT_eX]

[DOI]

Proceedings of the 17th Annual IEEE Conference on Computational Complexity, 2002

2001

Evasiveness of Subgraph Containment and Related Properties.

[BibT_eX]

[DOI]

Yaoyun Shi

Proceedings of the STACS 2001, 2001

Improved Lower Bounds on the Randomized Complexity of Graph Properties.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 28th International Colloquium, 2001

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

[BibT_eX]

[DOI]

Proceedings of the 42nd Annual Symposium on Foundations of Computer Science, 2001

Query Efficient PCPs with Perfect Completeness.

[BibT_eX]

[DOI]

Johan Håstad

Proceedings of the 42nd Annual Symposium on Foundations of Computer Science, 2001

2000

Parameterized Complexity of Finding Subgraphs with Hereditary Properties.

[BibT_eX]

[DOI]