Subhash Khot
According to our database^{1},
Subhash Khot
authored at least 103 papers
between 2001 and 2019.
Collaborative distances:
Collaborative distances:
Timeline
Legend:
Book In proceedings Article PhD thesis OtherLinks
Homepages:

at zbmath.org

at id.loc.gov
On csauthors.net:
Bibliography
2019
Improved 3LIN Hardness via Linear Label Cover.
Electronic Colloquium on Computational Complexity (ECCC), 2019
On Rich $2$to$1$ Games.
Electronic Colloquium on Computational Complexity (ECCC), 2019
Simultaneous MaxCut is harder to approximate than MaxCut.
Electronic Colloquium on Computational Complexity (ECCC), 2019
UGhardness to NPhardness by Losing Half.
Electronic Colloquium on Computational Complexity (ECCC), 2019
The AndoniKrauthgamerRazenshteyn characterization of sketchable norms fails for sketchable metrics.
Proceedings of the Thirtieth Annual ACMSIAM Symposium on Discrete Algorithms, 2019
2018
Pseudorandom Sets in Grassmann Graph have NearPerfect Expansion.
Electronic Colloquium on Computational Complexity (ECCC), 2018
Small Set Expansion in The Johnson Graph.
Electronic Colloquium on Computational Complexity (ECCC), 2018
Nearoptimal approximation algorithm for simultaneous MaxCut.
Proceedings of the TwentyNinth Annual ACMSIAM Symposium on Discrete Algorithms, 2018
2017
Hardness of Coloring 2Colorable 12Uniform Hypergraphs with 2^{(log n)Ømega(1)} Colors.
SIAM J. Comput., 2017
On NonOptimally Expanding Sets in Grassmann Graphs.
Electronic Colloquium on Computational Complexity (ECCC), 2017
An Improved Dictatorship Test with Perfect Completeness.
Electronic Colloquium on Computational Complexity (ECCC), 2017
2016
An Õ(n) Queries Adaptive Tester for Unateness.
Electronic Colloquium on Computational Complexity (ECCC), 2016
Approximating CSPs using LP Relaxation.
Electronic Colloquium on Computational Complexity (ECCC), 2016
On Independent Sets, 2to2 Games and Grassmann Graphs.
Electronic Colloquium on Computational Complexity (ECCC), 2016
Towards a Proof of the 2to1 Games Conjecture?
Electronic Colloquium on Computational Complexity (ECCC), 2016
An $\widetilde{O}(n)$ Queries Adaptive Tester for Unateness.
CoRR, 2016
Candidate hard unique game.
Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, 2016
Hardness of Approximation.
Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, 2016
Hardness of Bipartite Expansion.
Proceedings of the 24th Annual European Symposium on Algorithms, 2016
2015
The Unique Games Conjecture, Integrality Gap for Cut Problems and Embeddability of NegativeType Metrics into ℓ_{1}.
J. ACM, 2015
On Hardness of Approximating the Parameterized Clique Problem.
Electronic Colloquium on Computational Complexity (ECCC), 2015
On Monotonicity Testing and Boolean Isoperimetric type Theorems.
Electronic Colloquium on Computational Complexity (ECCC), 2015
2014
A Simple Deterministic Reduction for the Gap Minimum Distance of Code Problem.
IEEE Trans. Information Theory, 2014
Almost Polynomial Factor Hardness for Closest Vector Problem with Preprocessing.
SIAM J. Comput., 2014
Hardness of Coloring 2Colorable 12Uniform Hypergraphs with 2^{log nΩ(1)} Colors.
Electronic Colloquium on Computational Complexity (ECCC), 2014
Candidate Lasserre Integrality Gap For Unique Games.
Electronic Colloquium on Computational Complexity (ECCC), 2014
Hardness of Finding Independent Sets in 2Colorable and Almost 2Colorable Hypergraphs.
Proceedings of the TwentyFifth Annual ACMSIAM Symposium on Discrete Algorithms, 2014
Hardness of Coloring 2Colorable 12Uniform Hypergraphs with exp(log^{Omega(1)} n) Colors.
Proceedings of the 55th IEEE Annual Symposium on Foundations of Computer Science, 2014
2013
A TwoProver OneRound Game with Strong Soundness.
Theory of Computing, 2013
NPHardness of Approximately Solving Linear Equations over Reals.
SIAM J. Comput., 2013
Sharp kernel clustering algorithms and their associated Grothendieck inequalities.
Random Struct. Algorithms, 2013
A Characterization of Approximation Resistance.
Electronic Colloquium on Computational Complexity (ECCC), 2013
A Characterization of Strong Approximation Resistance.
Electronic Colloquium on Computational Complexity (ECCC), 2013
A characterization of approximation resistance for even kpartite CSPs.
Proceedings of the Innovations in Theoretical Computer Science, 2013
On Approximation Resistance of Predicates (Invited Talk).
Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2013
2012
The Complexity of Somewhat Approximation Resistant Predicates.
Electronic Colloquium on Computational Complexity (ECCC), 2012
Towards An Optimal Query Efficient PCP?
Electronic Colloquium on Computational Complexity (ECCC), 2012
2^{log1ε n} hardness for the closest vector problem with preprocessing.
Proceedings of the 44th Symposium on Theory of Computing Conference, 2012
Hardness of Finding Independent Sets in Almost qColorable Graphs.
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.
Theory of Computing, 2011
Combinatorial theorems about embedding trees on the real line.
Journal of Graph Theory, 2011
On the hardness of learning intersections of two halfspaces.
J. Comput. Syst. Sci., 2011
2^{log1έn} Hardness for Closest Vector Problem with Preprocessing.
Electronic Colloquium on Computational Complexity (ECCC), 2011
$2^{\log^{1\eps} n}$ Hardness for Closest Vector Problem with Preprocessing
CoRR, 2011
Grothendiecktype inequalities in combinatorial optimization
CoRR, 2011
Hardness of Approximating the Closest Vector Problem with PreProcessing.
Computational Complexity, 2011
2010
Inapproximability Results for Computational Problems on Lattices.
Proceedings of the LLL Algorithm  Survey and Applications, 2010
Hardness of Approximately Solving Linear Equations Over Reals.
Electronic Colloquium on Computational Complexity (ECCC), 2010
NPHardness of Approximately Solving Linear Equations Over Reals.
Electronic Colloquium on Computational Complexity (ECCC), 2010
Limits of Approximation Algorithms: PCPs and Unique Games (DIMACS Tutorial Lecture Notes)
CoRR, 2010
SDP Gaps for 2to1 and Other LabelCover Variants.
Proceedings of the Automata, Languages and Programming, 37th International Colloquium, 2010
Inapproximability of Hypergraph Vertex Cover and Applications to Scheduling Problems.
Proceedings of the Automata, Languages and Programming, 37th International Colloquium, 2010
Hardness of Finding Independent Sets in Almost 3Colorable Graphs.
Proceedings of the 51th Annual IEEE Symposium on Foundations of Computer Science, 2010
On the Unique Games Conjecture (Invited Survey).
Proceedings of the 25th Annual IEEE Conference on Computational Complexity, CCC 2010, 2010
Approximate Lasserre Integrality Gap for Unique Games.
Proceedings of the Approximation, 2010
2009
SDP Gaps and UGChardness for MaxCutGain.
Theory of Computing, 2009
On Agnostic Learning of Parities, Monomials, and Halfspaces.
SIAM J. Comput., 2009
SDP Integrality Gaps with Local ell_1Embeddability.
Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science, 2009
Optimal Long Code Test with One Free Bit.
Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science, 2009
2008
Linear Equations Modulo 2 and the L_{1} Diameter of Convex Bodies.
SIAM J. Comput., 2008
Vertex cover might be hard to approximate to within 2epsilon.
J. Comput. Syst. Sci., 2008
Inapproximability Results for Combinatorial Auctions with Submodular Utility Functions.
Algorithmica, 2008
On hardness of learning intersection of two halfspaces.
Proceedings of the 40th Annual ACM Symposium on Theory of Computing, 2008
Unique games on expanding constraint graphs are easy: extended abstract.
Proceedings of the 40th Annual ACM Symposium on Theory of Computing, 2008
Hardness of Minimizing and Learning DNF Expressions.
Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, 2008
Approximate Kernel Clustering.
Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, 2008
Minimizing Wide Range Regret with Time Selection Functions.
Proceedings of the 21st Annual Conference on Learning Theory, 2008
2007
Improved lower bounds on the randomized complexity of graph properties.
Random Struct. Algorithms, 2007
Hardness of Reconstructing Multivariate Polynomials over Finite Fields.
Electronic Colloquium on Computational Complexity (ECCC), 2007
Linear Equations Modulo 2 and the L1 Diameter of Convex Bodies.
Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2007), 2007
Hardness of Embedding Metric Spaces of Equal Size.
Proceedings of the Approximation, 2007
Approximation Algorithms for the MaxMin Allocation Problem.
Proceedings of the Approximation, 2007
2006
Ruling Out PTAS for Graph MinBisection, Dense kSubgraph, and Bipartite Clique.
SIAM J. Comput., 2006
Hardness of approximating the Shortest Vector Problem in high l_{p} norms.
J. Comput. Syst. Sci., 2006
New Results for Learning Noisy Parities and Halfspaces.
Electronic Colloquium on Computational Complexity (ECCC), 2006
Integrality gaps for sparsest cut and minimum linear arrangement problems.
Proceedings of the 38th Annual ACM Symposium on Theory of Computing, 2006
Better Inapproximability Results for MaxClique, Chromatic Number and Min3LinDeletion.
Proceedings of the Automata, Languages and Programming, 33rd International Colloquium, 2006
SDP gaps and UGChardness for MAXCUTGAIN.
Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), 2006
A 3Query NonAdaptive PCP with Perfect Completeness.
Proceedings of the 21st Annual IEEE Conference on Computational Complexity (CCC 2006), 2006
2005
Query Efficient PCPs with Perfect Completeness.
Theory of Computing, 2005
Guest column: inapproximability results via Long Code based PCPs.
SIGACT News, 2005
A New Multilayered PCP and the Hardness of Hypergraph Vertex Cover.
SIAM J. Comput., 2005
Hardness of approximating the shortest vector problem in lattices.
J. ACM, 2005
Optimal Inapproximability Results for MAXCUT and Other 2Variable CSPs?
Electronic Colloquium on Computational Complexity (ECCC), 2005
On earthmover distance, metric labeling, and 0extension
Electronic Colloquium on Computational Complexity (ECCC), 2005
Nonembeddability theorems via Fourier analysis.
Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005), 2005
On the Unique Games Conjecture.
Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005), 2005
Hardness of Max 3SAT with No Mixed Clauses.
Proceedings of the 20th Annual IEEE Conference on Computational Complexity (CCC 2005), 2005
2004
Cellprobe lower bounds for the partial match problem.
J. Comput. Syst. Sci., 2004
A new PCP outer verifier with applications to homogeneous linear equations and maxbisection.
Proceedings of the 36th Annual ACM Symposium on Theory of Computing, 2004
Ruling Out PTAS for Graph MinBisection, Densest Subgraph and Bipartite Clique.
Proceedings of the 45th Symposium on Foundations of Computer Science (FOCS 2004), 2004
2003
Fitting algebraic curves to noisy data.
J. Comput. Syst. Sci., 2003
Hardness of Approximating the Shortest Vector Problem in High L_{p} Norms.
Proceedings of the 44th Symposium on Foundations of Computer Science (FOCS 2003), 2003
Vertex Cover Might be Hard to Approximate to within 2\varepsilon.
Proceedings of the 18th Annual IEEE Conference on Computational Complexity (Complexity 2003), 2003
A Strong Inapproximability Gap for a Generalization of Minimum Bisection.
Proceedings of the 18th Annual IEEE Conference on Computational Complexity (Complexity 2003), 2003
NearOptimal Lower Bounds on the MultiParty Communication Complexity of Set Disjointness.
Proceedings of the 18th Annual IEEE Conference on Computational Complexity (Complexity 2003), 2003
2002
Parameterized complexity of finding subgraphs with hereditary properties.
Theor. Comput. Sci., 2002
Vertex Cover on kUniform Hypergraphs is Hard to Approximate within Factor (k3epsilon)
Electronic Colloquium on Computational Complexity (ECCC), 2002
On the power of unique 2prover 1round games.
Proceedings of the Proceedings on 34th Annual ACM Symposium on Theory of Computing, 2002
Hardness results for approximate hypergraph coloring.
Proceedings of the Proceedings on 34th Annual ACM Symposium on Theory of Computing, 2002
Hardness Results for Coloring 3 Colorable 3 Uniform Hypergraphs.
Proceedings of the 43rd Symposium on Foundations of Computer Science (FOCS 2002), 2002
2001
Evasiveness of Subgraph Containment and Related Properties.
SIAM J. Comput., 2001
Improved Inaproximability Results for MaxClique, Chromatic Number and Approximate Graph Coloring.
Proceedings of the 42nd Annual Symposium on Foundations of Computer Science, 2001