Subhash Khot

205 papers A* 60A 21Misc 1Journal 108Unranked 14
YearRankTypeTitle / Venue / Authors
2025 J jnl
An Analytical Approach to Parallel Repetition via CSP Inverse Theorems.
CoRR
Amey Bhangale, Mark Braverman, Subhash Khot, Yang P. Liu, Dor Minzer, Kunal Mittal
2025 J jnl
An Analytical Approach to Parallel Repetition via CSP Inverse Theorems.
Electron. Colloquium Comput. Complex.
Amey Bhangale, Mark Braverman, Subhash Khot, Yang P. Liu, Dor Minzer, Kunal Mittal
2025 A conf
Biased Linearity Testing in the 1% Regime.
CCC
Subhash Khot, Kunal Mittal
2025 J jnl
Biased Linearity Testing in the 1% Regime.
CoRR
Subhash Khot, Kunal Mittal
2025 J jnl
Biased Linearity Testing in the 1% Regime.
Electron. Colloquium Comput. Complex.
Subhash Khot, Kunal Mittal
2025 A* conf
Maximum Span Hypothesis: A Potentially Weaker Assumption than Gap-ETH for Parameterized Complexity.
SODA
Karthik C. S., Subhash Khot
2025 A* conf
On Approximability of Satisfiable k-CSPs: V.
STOC
Amey Bhangale, Subhash Khot, Dor Minzer
2025 A* conf
On Inverse Theorems and Combinatorial Lines.
FOCS
Amey Bhangale, Subhash Khot, Yang P. Liu, Dor Minzer
2025 J jnl
On approximability of Satisfiable k-CSPs: I.
Comput. Complex.
Amey Bhangale, Subhash Khot, Dor Minzer
2025 J jnl
On approximability of satisfiable $\boldsymbol {k}$ -CSPs: II.
Comb. Probab. Comput.
Amey Bhangale, Subhash Khot, Dor Minzer
2025 A* conf
Parallel Repetition for 3-Player XOR Games.
STOC
Amey Bhangale, Mark Braverman, Subhash Khot, Yang P. Liu, Dor Minzer
2025 J jnl
Parallel Repetition for 3-Player XOR Games.
Electron. Colloquium Comput. Complex.
Amey Bhangale, Mark Braverman, Subhash Khot, Yang P. Liu, Dor Minzer
2025 J jnl
Small Set Expansion in the Johnson Graph.
Theory Comput.
Subhash Khot, Dor Minzer, Dana Moshkovitz, Muli Safra
2024 J jnl
On Approximability of Satisfiable
CoRR
Amey Bhangale, Subhash Khot, Yang P. Liu, Dor Minzer
2024 J jnl
On Approximability of Satisfiable
CoRR
Amey Bhangale, Subhash Khot, Yang P. Liu, Dor Minzer
2024 A* conf
On Approximability of Satisfiable k-CSPs: IV.
STOC
Amey Bhangale, Subhash Khot, Dor Minzer
2024 J jnl
On Approximability of Satisfiable k-CSPs: V.
CoRR
Amey Bhangale, Subhash Khot, Dor Minzer
2024 J jnl
On Approximability of Satisfiable k-CSPs: V.
Electron. Colloquium Comput. Complex.
Amey Bhangale, Subhash Khot, Dor Minzer
2024 J jnl
On Approximability of Satisfiable k-CSPs: VI.
Electron. Colloquium Comput. Complex.
Amey Bhangale, Subhash Khot, Yang P. Liu, Dor Minzer
2024 J jnl
On Approximability of Satisfiable k-CSPs: VII.
Electron. Colloquium Comput. Complex.
Amey Bhangale, Subhash Khot, Yang P. Liu, Dor Minzer
2024 J jnl
Parallel Repetition for 3-Player XOR Games.
CoRR
Amey Bhangale, Mark Braverman, Subhash Khot, Yang P. Liu, Dor Minzer
2024 A conf
Parallel Repetition of k-Player Projection Games.
APPROX/RANDOM
Amey Bhangale, Mark Braverman, Subhash Khot, Yang P. Liu, Dor Minzer
2024 J jnl
Reasonable Bounds for Combinatorial Lines of Length Three.
CoRR
Amey Bhangale, Subhash Khot, Yang P. Liu, Dor Minzer
2024 J jnl
Reasonable Bounds for Combinatorial Lines of Length Three.
Electron. Colloquium Comput. Complex.
Amey Bhangale, Subhash Khot, Yang P. Liu, Dor Minzer
2023 J jnl
Effective Bounds for Restricted $3$-Arithmetic Progressions in $\mathbb{F}_p^n$.
Electron. Colloquium Comput. Complex.
Amey Bhangale, Subhash Khot, Dor Minzer
2023 J jnl
Effective Bounds for Restricted 3-Arithmetic Progressions in F
CoRR
Amey Bhangale, Subhash Khot, Dor Minzer
2023 A conf
Improved Monotonicity Testers via Hypercube Embeddings.
ITCS
Mark Braverman, Subhash Khot, Guy Kindler, Dor Minzer
2023 J jnl
On Approximability of Satisfiable
Electron. Colloquium Comput. Complex.
Amey Bhangale, Subhash Khot, Dor Minzer
2023 J jnl
On Approximability of Satisfiable
Electron. Colloquium Comput. Complex.
Amey Bhangale, Subhash Khot, Dor Minzer
2023 A* conf
On Approximability of Satisfiable k-CSPs: II.
STOC
Amey Bhangale, Subhash Khot, Dor Minzer
2023 A* conf
On Approximability of Satisfiable k-CSPs: III.
STOC
Amey Bhangale, Subhash Khot, Dor Minzer
2023 J jnl
On Approximability of Satisfiable k-CSPs: IV.
CoRR
Amey Bhangale, Subhash Khot, Dor Minzer
2023 J jnl
On Approximability of Satisfiable k-CSPs: IV.
Electron. Colloquium Comput. Complex.
Amey Bhangale, Subhash Khot, Dor Minzer
2023 A* conf
Parallel Repetition for the GHZ Game: Exponential Decay.
FOCS
Mark Braverman, Subhash Khot, Dor Minzer
2023 J jnl
Parallel Repetition of k-Player Projection Games.
CoRR
Amey Bhangale, Mark Braverman, Subhash Khot, Yang P. Liu, Dor Minzer
2023 J jnl
Parallel Repetition of k-Player Projection Games.
Electron. Colloquium Comput. Complex.
Amey Bhangale, Mark Braverman, Subhash Khot, Yang P. Liu, Dor Minzer
2022 A conf
Almost Polynomial Factor Inapproximability for Parameterized k-Clique.
CCC
Karthik C. S., Subhash Khot
2022 J jnl
Improved Monotonicity Testers via Hypercube Embeddings.
CoRR
Mark Braverman, Subhash Khot, Guy Kindler, Dor Minzer
2022 J jnl
On Approximability of Satisfiable
Electron. Colloquium Comput. Complex.
Amey Bhangale, Subhash Khot, Dor Minzer
2022 A* conf
On approximability of satisfiable
STOC
Amey Bhangale, Subhash Khot, Dor Minzer
2022 J jnl
Parallel Repetition for the GHZ Game: Exponential Decay.
CoRR
Mark Braverman, Subhash Khot, Dor Minzer
2022 J jnl
Parallel Repetition for the GHZ Game: Exponential Decay.
Electron. Colloquium Comput. Complex.
Mark Braverman, Subhash Khot, Dor Minzer
2022 J jnl
UG-hardness to NP-hardness by Losing Half.
Theory Comput.
Amey Bhangale, Subhash Khot
2021 J jnl
Almost Polynomial Factor Inapproximability for Parameterized k-Clique.
CoRR
Karthik C. S., Subhash Khot
2021 A* conf
An Invariance Principle for the Multi-slice, with Applications.
FOCS
Mark Braverman, Subhash Khot, Noam Lifshitz, Dor Minzer
2021 J jnl
An Invariance Principle for the Multi-slice, with Applications.
CoRR
Mark Braverman, Subhash Khot, Noam Lifshitz, Dor Minzer
2021 A conf
On Rich 2-to-1 Games.
ITCS
Mark Braverman, Subhash Khot, Dor Minzer
2021 A* conf
Optimal inapproximability of satisfiable k-LIN over non-abelian groups.
STOC
Amey Bhangale, Subhash Khot
2021 A conf
Theorems of KKL, Friedgut, and Talagrand via Random Restrictions and Log-Sobolev Inequality.
ITCS
Esty Kelman, Subhash Khot, Guy Kindler, Dor Minzer, Muli Safra
2020 J jnl
Optimal Inapproximability of Satisfiable k-LIN over Non-Abelian Groups.
CoRR
Amey Bhangale, Subhash Khot
2020 J jnl
Optimal Inapproximability of Satisfiable k-LIN over Non-Abelian Groups.
Electron. Colloquium Comput. Complex.
Amey Bhangale, Subhash Khot
2020 A conf
Simultaneous Max-Cut Is Harder to Approximate Than Max-Cut.
CCC
Amey Bhangale, Subhash Khot
2020 J jnl
Theorems of KKL, Friedgut, and Talagrand via Random Restrictions and Log-Sobolev Inequality.
Electron. Colloquium Comput. Complex.
Esty Kelman, Subhash Khot, Guy Kindler, Dor Minzer, Muli Safra
2019 — conf
Improved 3LIN Hardness via Linear Label Cover.
APPROX-RANDOM
Prahladh Harsha, Subhash Khot, Euiwoong Lee, Devanathan Thiruvenkatachari
2019 J jnl
Improved 3LIN Hardness via Linear Label Cover.
Electron. Colloquium Comput. Complex.
Prahladh Harsha, Subhash Khot, Euiwoong Lee, Devanathan Thiruvenkatachari
2019 J jnl
On Rich $2$-to-$1$ Games.
Electron. Colloquium Comput. Complex.
Mark Braverman, Subhash Khot, Dor Minzer
2019 J jnl
Simultaneous Max-Cut is harder to approximate than Max-Cut.
Electron. Colloquium Comput. Complex.
Amey Bhangale, Subhash Khot
2019 A* conf
The Andoni-Krauthgamer-Razenshteyn characterization of sketchable norms fails for sketchable metrics.
SODA
Subhash Khot, Assaf Naor
2019 A conf
UG-Hardness to NP-Hardness by Losing Half.
CCC
Amey Bhangale, Subhash Khot
2019 J jnl
UG-hardness to NP-hardness by Losing Half.
Electron. Colloquium Comput. Complex.
Amey Bhangale, Subhash Khot
2018 A* conf
Near-optimal approximation algorithm for simultaneous Max-Cut.
SODA
Amey Bhangale, Subhash Khot, Swastik Kopparty, Sushant Sachdeva, Devanathan Thiruvenkatachari
2018 J jnl
Near-optimal approximation algorithm for simultaneous Max-Cut.
CoRR
Amey Bhangale, Subhash Khot, Swastik Kopparty, Sushant Sachdeva, Devanathan Thiruvenkatachari
2018 J jnl
On Monotonicity Testing and Boolean Isoperimetric-type Theorems.
SIAM J. Comput.
Subhash Khot, Dor Minzer, Muli Safra
2018 A* conf
On non-optimally expanding sets in Grassmann graphs.
STOC
Irit Dinur, Subhash Khot, Guy Kindler, Dor Minzer, Muli Safra
2018 A* conf
Pseudorandom Sets in Grassmann Graph Have Near-Perfect Expansion.
FOCS
Subhash Khot, Dor Minzer, Muli Safra
2018 J jnl
Pseudorandom Sets in Grassmann Graph have Near-Perfect Expansion.
Electron. Colloquium Comput. Complex.
Subhash Khot, Dor Minzer, Muli Safra
2018 J jnl
Small Set Expansion in The Johnson Graph.
Electron. Colloquium Comput. Complex.
Subhash Khot, Dor Minzer, Dana Moshkovitz, Muli Safra
2018 J jnl
The Andoni-Krauthgamer-Razenshteyn characterization of sketchable norms fails for sketchable metrics.
CoRR
Subhash Khot, Assaf Naor
2018 A* conf
Towards a proof of the 2-to-1 games conjecture?
STOC
Irit Dinur, Subhash Khot, Guy Kindler, Dor Minzer, Muli Safra
2017 — conf
An Improved Dictatorship Test with Perfect Completeness.
FSTTCS
Amey Bhangale, Subhash Khot, Devanathan Thiruvenkatachari
2017 J jnl
An Improved Dictatorship Test with Perfect Completeness.
CoRR
Amey Bhangale, Subhash Khot, Devanathan Thiruvenkatachari
2017 J jnl
An Improved Dictatorship Test with Perfect Completeness.
Electron. Colloquium Comput. Complex.
Amey Bhangale, Subhash Khot, Devanathan Thiruvenkatachari
2017 J jnl
Hardness of Coloring 2-Colorable 12-Uniform Hypergraphs with 2
SIAM J. Comput.
Subhash Khot, Rishi Saket
2017 J jnl
On Non-Optimally Expanding Sets in Grassmann Graphs.
Electron. Colloquium Comput. Complex.
Irit Dinur, Subhash Khot, Guy Kindler, Dor Minzer, Muli Safra
2017 A* conf
On independent sets, 2-to-2 games, and Grassmann graphs.
STOC
Subhash Khot, Dor Minzer, Muli Safra
2016 J jnl
An $\widetilde{O}(n)$ Queries Adaptive Tester for Unateness.
CoRR
Subhash Khot, Igor Shinkar
2016 — conf
An ~O(n) Queries Adaptive Tester for Unateness.
APPROX-RANDOM
Subhash Khot, Igor Shinkar
2016 J jnl
An Õ(n) Queries Adaptive Tester for Unateness.
Electron. Colloquium Comput. Complex.
Subhash Khot, Igor Shinkar
2016 J jnl
Approximating CSPs using LP Relaxation.
Electron. Colloquium Comput. Complex.
Subhash Khot, Rishi Saket
2016 A* conf
Candidate hard unique game.
STOC
Subhash Khot, Dana Moshkovitz
2016 A* conf
Hardness of Approximation.
ICALP
Subhash Khot
2016 A conf
Hardness of Bipartite Expansion.
ESA
Subhash Khot, Rishi Saket
2016 A conf
On Hardness of Approximating the Parameterized Clique Problem.
ITCS
Subhash Khot, Igor Shinkar
2016 J jnl
On Independent Sets, 2-to-2 Games and Grassmann Graphs.
Electron. Colloquium Comput. Complex.
Subhash Khot, Dor Minzer, Muli Safra
2016 J jnl
Towards a Proof of the 2-to-1 Games Conjecture?
Electron. Colloquium Comput. Complex.
Irit Dinur, Subhash Khot, Guy Kindler, Dor Minzer, Muli Safra
2015 — conf
Approximating CSPs Using LP Relaxation.
ICALP (1)
Subhash Khot, Rishi Saket
2015 J jnl
On Hardness of Approximating the Parameterized Clique Problem.
Electron. Colloquium Comput. Complex.
Subhash Khot, Igor Shinkar
2015 A* conf
On Monotonicity Testing and Boolean Isoperimetric Type Theorems.
FOCS
Subhash Khot, Dor Minzer, Muli Safra
2015 J jnl
On Monotonicity Testing and Boolean Isoperimetric type Theorems.
Electron. Colloquium Comput. Complex.
Subhash Khot, Dor Minzer, Muli Safra
2015 J jnl
The Unique Games Conjecture, Integrality Gap for Cut Problems and Embeddability of Negative-Type Metrics into ℓ
J. ACM
Subhash Khot, Nisheeth K. Vishnoi
2014 J jnl
A Simple Deterministic Reduction for the Gap Minimum Distance of Code Problem.
IEEE Trans. Inf. Theory
Per Austrin, Subhash Khot
2014 A* conf
A characterization of strong approximation resistance.
STOC
Subhash Khot, Madhur Tulsiani, Pratik Worah
2014 J jnl
Almost Polynomial Factor Hardness for Closest Vector Problem with Preprocessing.
SIAM J. Comput.
Subhash Khot, Preyas Popat, Nisheeth K. Vishnoi
2014 J jnl
Candidate Lasserre Integrality Gap For Unique Games.
Electron. Colloquium Comput. Complex.
Subhash Khot, Dana Moshkovitz
2014 J jnl
Hardness of Coloring 2-Colorable 12-Uniform Hypergraphs with 2
Electron. Colloquium Comput. Complex.
Subhash Khot, Rishi Saket
2014 A* conf
Hardness of Coloring 2-Colorable 12-Uniform Hypergraphs with exp(log^{Omega(1)} n) Colors.
FOCS
Subhash Khot, Rishi Saket
2014 A* conf
Hardness of Finding Independent Sets in 2-Colorable and Almost 2-Colorable Hypergraphs.
SODA
Subhash Khot, Rishi Saket
2014 — conf
The Complexity of Somewhat Approximation Resistant Predicates.
ICALP (1)
Subhash Khot, Madhur Tulsiani, Pratik Worah
2013 J jnl
A Characterization of Approximation Resistance for Even $k$-Partite CSPs
CoRR
Per Austrin, Subhash Khot
2013 J jnl
A Characterization of Approximation Resistance.
Electron. Colloquium Comput. Complex.
Subhash Khot, Madhur Tulsiani, Pratik Worah
2013 J jnl
A Characterization of Strong Approximation Resistance
CoRR
Subhash Khot, Madhur Tulsiani, Pratik Worah
2013 J jnl
A Characterization of Strong Approximation Resistance.
Electron. Colloquium Comput. Complex.
Subhash Khot, Madhur Tulsiani, Pratik Worah
2013 J jnl
A Two-Prover One-Round Game with Strong Soundness.
Theory Comput.
Subhash Khot, Muli Safra
2013 A conf
A characterization of approximation resistance for even k-partite CSPs.
ITCS
Per Austrin, Subhash Khot
2013 J jnl
Hardness of Finding Independent Sets in 2-Colorable and Almost 2-Colorable Hypergraphs.
CoRR
Subhash Khot, Rishi Saket
2013 — conf
On Approximation Resistance of Predicates (Invited Talk).
FSTTCS
Subhash Khot
2013 J jnl
Sharp kernel clustering algorithms and their associated Grothendieck inequalities.
Random Struct. Algorithms
Subhash Khot, Assaf Naor
2013 J jnl
The Unique Games Conjecture, Integrality Gap for Cut Problems and Embeddability of Negative Type Metrics into ℓ
CoRR
Subhash Khot, Nisheeth K. Vishnoi
2013 A conf
Towards an optimal query efficient PCP?
ITCS
Subhash Khot, Muli Safra, Madhur Tulsiani
2012 A* conf
2
STOC
Subhash Khot, Preyas Popat, Nisheeth K. Vishnoi
2012 A* conf
Hardness of Finding Independent Sets in Almost q-Colorable Graphs.
FOCS
Subhash Khot, Rishi Saket
2012 J jnl
The Complexity of Somewhat Approximation Resistant Predicates.
Electron. Colloquium Comput. Complex.
Subhash Khot, Madhur Tulsiani, Pratik Worah
2012 J jnl
Towards An Optimal Query Efficient PCP?
Electron. Colloquium Comput. Complex.
Subhash Khot, Muli Safra, Madhur Tulsiani
2011 J jnl
$2^{\log^{1-\eps} n}$ Hardness for Closest Vector Problem with Preprocessing
CoRR
Subhash Khot, Preyas Popat, Nisheeth K. Vishnoi
2011 J jnl
2
Electron. Colloquium Comput. Complex.
Subhash Khot, Preyas Popat, Nisheeth K. Vishnoi
2011 — conf
A Simple Deterministic Reduction for the Gap Minimum Distance of Code Problem.
ICALP (1)
Per Austrin, Subhash Khot
2011 A* conf
A Two Prover One Round Game with Strong Soundness.
FOCS
Subhash Khot, Muli Safra
2011 J jnl
Combinatorial theorems about embedding trees on the real line.
J. Graph Theory
Amit Chakrabarti, Subhash Khot
2011 J jnl
Grothendieck-type inequalities in combinatorial optimization
CoRR
Subhash Khot, Assaf Naor
2011 J jnl
Hardness of Approximating the Closest Vector Problem with Pre-Processing.
Comput. Complex.
Mikhail Alekhnovich, Subhash Khot, Guy Kindler, Nisheeth K. Vishnoi
2011 J jnl
Inapproximability of Vertex Cover and Independent Set in Bounded Degree Graphs.
Theory Comput.
Per Austrin, Subhash Khot, Muli Safra
2011 A* conf
NP-hardness of approximately solving linear equations over reals.
STOC
Subhash Khot, Dana Moshkovitz
2011 J jnl
On the hardness of learning intersections of two halfspaces.
J. Comput. Syst. Sci.
Subhash Khot, Rishi Saket
2010 J jnl
A Simple Deterministic Reduction for the Gap Minimum Distance of Code Problem
CoRR
Per Austrin, Subhash Khot
2010 — conf
Approximate Lasserre Integrality Gap for Unique Games.
APPROX-RANDOM
Subhash Khot, Preyas Popat, Rishi Saket
2010 J jnl
Hardness of Approximately Solving Linear Equations Over Reals.
Electron. Colloquium Comput. Complex.
Dana Moshkovitz, Subhash Khot
2010 A* conf
Hardness of Finding Independent Sets in Almost 3-Colorable Graphs.
FOCS
Irit Dinur, Subhash Khot, Will Perkins, Muli Safra
2010 J jnl
Hardness of Reconstructing Multivariate Polynomials over Finite Fields.
SIAM J. Comput.
Parikshit Gopalan, Subhash Khot, Rishi Saket
2010 — ch.
Inapproximability Results for Computational Problems on Lattices.
The LLL Algorithm
Subhash Khot
2010 — conf
Inapproximability of Hypergraph Vertex Cover and Applications to Scheduling Problems.
ICALP (1)
Nikhil Bansal, Subhash Khot
2010 J jnl
Limits of Approximation Algorithms: PCPs and Unique Games (DIMACS Tutorial Lecture Notes)
CoRR
Prahladh Harsha, Moses Charikar, Matthew Andrews, Sanjeev Arora, Subhash Khot, Dana Moshkovitz, Lisa Zhang, Ashkan Aazami, Dev Desai, Igor Gorodezky, Geetha Jagannathan, Alexander S. Kulikov, Darakhshan J. Mir, Alantha Newman, Aleksandar Nikolov, David Pritchard, Gwen Spencer
2010 J jnl
NP-Hardness of Approximately Solving Linear Equations Over Reals.
Electron. Colloquium Comput. Complex.
Subhash Khot, Dana Moshkovitz
2010 A conf
On the Unique Games Conjecture (Invited Survey).
CCC
Subhash Khot
2010 — conf
SDP Gaps for 2-to-1 and Other Label-Cover Variants.
ICALP (1)
Venkatesan Guruswami, Subhash Khot, Ryan O'Donnell, Preyas Popat, Madhur Tulsiani, Yi Wu
2010 A* conf
Sharp Kernel Clustering Algorithms and Their Associated Grothendieck Inequalities.
SODA
Subhash Khot, Assaf Naor
2009 A conf
Inapproximability of Vertex Cover and Independent Set in Bounded Degree Graphs.
CCC
Per Austrin, Subhash Khot, Muli Safra
2009 J jnl
On Agnostic Learning of Parities, Monomials, and Halfspaces.
SIAM J. Comput.
Vitaly Feldman, Parikshit Gopalan, Subhash Khot, Ashok Kumar Ponnuswami
2009 J jnl
On Earthmover Distance, Metric Labeling, and 0-Extension.
SIAM J. Comput.
Howard J. Karloff, Subhash Khot, Aranyak Mehta, Yuval Rabani
2009 A* conf
Optimal Long Code Test with One Free Bit.
FOCS
Nikhil Bansal, Subhash Khot
2009 J jnl
SDP Gaps and UGC-hardness for Max-Cut-Gain.
Theory Comput.
Subhash Khot, Ryan O'Donnell
2009 A* conf
SDP Integrality Gaps with Local ell_1-Embeddability.
FOCS
Subhash Khot, Rishi Saket
2009 J jnl
Sharp kernel clustering algorithms and their associated Grothendieck inequalities
CoRR
Subhash Khot, Assaf Naor
2008 A* conf
Approximate Kernel Clustering.
FOCS
Subhash Khot, Assaf Naor
2008 J jnl
Approximate kernel clustering
CoRR
Subhash Khot, Assaf Naor
2008 A* conf
Hardness of Minimizing and Learning DNF Expressions.
FOCS
Subhash Khot, Rishi Saket
2008 J jnl
Inapproximability Results for Combinatorial Auctions with Submodular Utility Functions.
Algorithmica
Subhash Khot, Richard J. Lipton, Evangelos Markakis, Aranyak Mehta
2008 J jnl
Linear Equations Modulo 2 and the L
SIAM J. Comput.
Subhash Khot, Assaf Naor
2008 A* conf
Minimizing Wide Range Regret with Time Selection Functions.
COLT
Subhash Khot, Ashok Kumar Ponnuswami
2008 A* conf
On hardness of learning intersection of two halfspaces.
STOC
Subhash Khot, Rishi Saket
2008 A* conf
Unique games on expanding constraint graphs are easy: extended abstract.
STOC
Sanjeev Arora, Subhash Khot, Alexandra Kolla, David Steurer, Madhur Tulsiani, Nisheeth K. Vishnoi
2008 J jnl
Vertex cover might be hard to approximate to within 2-epsilon.
J. Comput. Syst. Sci.
Subhash Khot, Oded Regev
2007 — conf
Approximation Algorithms for the Max-Min Allocation Problem.
APPROX-RANDOM
Subhash Khot, Ashok Kumar Ponnuswami
2007 — conf
Hardness of Embedding Metric Spaces of Equal Size.
APPROX-RANDOM
Subhash Khot, Rishi Saket
2007 A* conf
Hardness of Reconstructing Multivariate Polynomials over Finite Fields.
FOCS
Parikshit Gopalan, Subhash Khot, Rishi Saket
2007 J jnl
Hardness of Reconstructing Multivariate Polynomials over Finite Fields.
Electron. Colloquium Comput. Complex.
Parikshit Gopalan, Subhash Khot, Rishi Saket
2007 J jnl
Improved lower bounds on the randomized complexity of graph properties.
Random Struct. Algorithms
Amit Chakrabarti, Subhash Khot
2007 A* conf
Linear Equations Modulo 2 and the L1 Diameter of Convex Bodies.
FOCS
Subhash Khot, Assaf Naor
2007 J jnl
Optimal Inapproximability Results for MAX-CUT and Other 2-Variable CSPs?.
SIAM J. Comput.
Subhash Khot, Guy Kindler, Elchanan Mossel, Ryan O'Donnell
2006 A conf
A 3-Query Non-Adaptive PCP with Perfect Completeness.
CCC
Subhash Khot, Rishi Saket
2006 — conf
Better Inapproximability Results for MaxClique, Chromatic Number and Min-3Lin-Deletion.
ICALP (1)
Subhash Khot, Ashok Kumar Ponnuswami
2006 J jnl
Hardness of approximating the Shortest Vector Problem in high
J. Comput. Syst. Sci.
Subhash Khot
2006 A* conf
Integrality gaps for sparsest cut and minimum linear arrangement problems.
STOC
Nikhil R. Devanur, Subhash Khot, Rishi Saket, Nisheeth K. Vishnoi
2006 A* conf
New Results for Learning Noisy Parities and Halfspaces.
FOCS
Vitaly Feldman, Parikshit Gopalan, Subhash Khot, Ashok Kumar Ponnuswami
2006 J jnl
New Results for Learning Noisy Parities and Halfspaces.
Electron. Colloquium Comput. Complex.
Vitaly Feldman, Parikshit Gopalan, Subhash Khot, Ashok Kumar Ponnuswami
2006 A* conf
On earthmover distance, metric labeling, and 0-extension.
STOC
Howard J. Karloff, Subhash Khot, Aranyak Mehta, Yuval Rabani
2006 J jnl
Ruling Out PTAS for Graph Min-Bisection, Dense k-Subgraph, and Bipartite Clique.
SIAM J. Comput.
Subhash Khot
2006 A* conf
SDP gaps and UGC-hardness for MAXCUTGAIN.
FOCS
Subhash Khot, Ryan O'Donnell
2005 J jnl
A New Multilayered PCP and the Hardness of Hypergraph Vertex Cover.
SIAM J. Comput.
Irit Dinur, Venkatesan Guruswami, Subhash Khot, Oded Regev
2005 J jnl
Guest column: inapproximability results via Long Code based PCPs.
SIGACT News
Subhash Khot
2005 A* conf
Hardness of Approximating the Closest Vector Problem with Pre-Processing.
FOCS
Mikhail Alekhnovich, Subhash Khot, Guy Kindler, Nisheeth K. Vishnoi
2005 A conf
Hardness of Max 3SAT with No Mixed Clauses.
CCC
Venkatesan Guruswami, Subhash Khot
2005 J jnl
Hardness of approximating the shortest vector problem in lattices.
J. ACM
Subhash Khot
2005 — conf
Inapproximability Results for Combinatorial Auctions with Submodular Utility Functions.
WINE
Subhash Khot, Richard J. Lipton, Evangelos Markakis, Aranyak Mehta
2005 A* conf
Nonembeddability theorems via Fourier analysis.
FOCS
Subhash Khot, Assaf Naor
2005 J jnl
On earthmover distance, metric labeling, and 0-extension
Electron. Colloquium Comput. Complex.
Howard J. Karloff, Subhash Khot, Aranyak Mehta, Yuval Rabani
2005 A* conf
On the Unique Games Conjecture.
FOCS
Subhash Khot
2005 J jnl
Optimal Inapproximability Results for MAX-CUT and Other 2-Variable CSPs?
Electron. Colloquium Comput. Complex.
Guy Kindler, Ryan O'Donnell, Subhash Khot, Elchanan Mossel
2005 J jnl
Query Efficient PCPs with Perfect Completeness.
Theory Comput.
Johan Håstad, Subhash Khot
2005 A* conf
The Unique Games Conjecture, Integrality Gap for Cut Problems and Embeddability of Negative Type Metrics into l
FOCS
Subhash Khot, Nisheeth K. Vishnoi
2004 A* conf
A new PCP outer verifier with applications to homogeneous linear equations and max-bisection.
STOC
Jonas Holmerin, Subhash Khot
2004 J jnl
Cell-probe lower bounds for the partial match problem.
J. Comput. Syst. Sci.
T. S. Jayram, Subhash Khot, Ravi Kumar, Yuval Rabani
2004 A* conf
Hardness of Approximating the Shortest Vector Problem in Lattices.
FOCS
Subhash Khot
2004 A* conf
Optimal Inapproximability Results for Max-Cut and Other 2-Variable CSPs?
FOCS
Subhash Khot, Guy Kindler, Elchanan Mossel, Ryan O'Donnell
2004 A* conf
Ruling Out PTAS for Graph Min-Bisection, Densest Subgraph and Bipartite Clique.
FOCS
Subhash Khot
2003 J jnl
A New Multilayered PCP and the Hardness of Hypergraph Vertex Cover
CoRR
Irit Dinur, Venkatesan Guruswami, Subhash Khot, Oded Regev
2003 A conf
A Strong Inapproximability Gap for a Generalization of Minimum Bisection.
CCC
Jonas Holmerin, Subhash Khot
2003 A* conf
A new multilayered PCP and the hardness of hypergraph vertex cover.
STOC
Irit Dinur, Venkatesan Guruswami, Subhash Khot, Oded Regev
2003 A* conf
Cell-probe lower bounds for the partial match problem.
STOC
T. S. Jayram, Subhash Khot, Ravi Kumar, Yuval Rabani
2003 J jnl
Fitting algebraic curves to noisy data.
J. Comput. Syst. Sci.
Sanjeev Arora, Subhash Khot
2003 A* conf
Hardness of Approximating the Shortest Vector Problem in High L
FOCS
Subhash Khot
2003 A conf
Near-Optimal Lower Bounds on the Multi-Party Communication Complexity of Set Disjointness.
CCC
Amit Chakrabarti, Subhash Khot, Xiaodong Sun
2003 A conf
Vertex Cover Might be Hard to Approximate to within 2-\varepsilon.
CCC
Subhash Khot, Oded Regev
2002 A* conf
Fitting algebraic curves to noisy data.
STOC
Sanjeev Arora, Subhash Khot
2002 A* conf
Hardness Results for Coloring 3 -Colorable 3 -Uniform Hypergraphs.
FOCS
Subhash Khot
2002 A* conf
Hardness results for approximate hypergraph coloring.
STOC
Subhash Khot
2002 A conf
On the Power of Unique 2-Prover 1-Round Games.
CCC
Subhash Khot
2002 A* conf
On the power of unique 2-prover 1-round games.
STOC
Subhash Khot
2002 J jnl
Parameterized complexity of finding subgraphs with hereditary properties.
Theor. Comput. Sci.
Subhash Khot, Venkatesh Raman
2002 J jnl
Vertex Cover on k-Uniform Hypergraphs is Hard to Approximate within Factor (k-3-epsilon)
Electron. Colloquium Comput. Complex.
Irit Dinur, Venkatesan Guruswami, Subhash Khot
2001 A conf
Evasiveness of Subgraph Containment and Related Properties.
STACS
Amit Chakrabarti, Subhash Khot, Yaoyun Shi
2001 J jnl
Evasiveness of Subgraph Containment and Related Properties.
SIAM J. Comput.
Amit Chakrabarti, Subhash Khot, Yaoyun Shi
2001 A* conf
Improved Inaproximability Results for MaxClique, Chromatic Number and Approximate Graph Coloring.
FOCS
Subhash Khot
2001 A* conf
Improved Lower Bounds on the Randomized Complexity of Graph Properties.
ICALP
Amit Chakrabarti, Subhash Khot
2001 A* conf
Query Efficient PCPs with Perfect Completeness.
FOCS
Johan Håstad, Subhash Khot
2000 Misc conf
Parameterized Complexity of Finding Subgraphs with Hereditary Properties.
COCOON
Subhash Khot, Venkatesh Raman