Person:430831

Available identifiers

zbMath Open khot.subhash-aDBLP25/1492WikidataQ7631228 ScholiaQ7631228MaRDI QIDQ430831

List of research outcomes

Publication	Date of Publication	Type
Improved monotonicity testers via hypercube embeddings	2024-09-25	Paper
Almost polynomial factor inapproximability for parameterized \(k\)-clique	2024-07-05	Paper
On approximability of satisfiable k-CSPs. II	2024-05-08	Paper
On approximability of satisfiable k-CSPs. III	2024-05-08	Paper
On approximability of satisfiable k -CSPs: I	2023-12-08	Paper
Optimal inapproximability of satisfiable k-LIN over non-abelian groups	2023-11-14	Paper
Effective Bounds for Restricted $3$-Arithmetic Progressions in $\mathbb{F}_p^n$	2023-08-12	Paper
On Approximability of Satisfiable k-CSPs: IV	2023-07-30	Paper
Pseudorandom sets in Grassmann graph have near-perfect expansion	2023-05-31	Paper
https://portal.mardi4nfdi.de/entity/Q5875460	2023-02-03	Paper
Improved Monotonicity Testers via Hypercube Embeddings	2022-11-16	Paper
UG-hardness to NP-hardness by losing half	2022-07-27	Paper
Simultaneous max-cut is harder to approximate than max-cut	2022-07-21	Paper
https://portal.mardi4nfdi.de/entity/Q5077147	2022-05-18	Paper
The Andoni–Krauthgamer–Razenshteyn Characterization of Sketchable Norms Fails for Sketchable Metrics	2021-12-14	Paper
On the proof of the 2-to-2 Games Conjecture	2021-12-09	Paper
An Invariance Principle for the Multi-slice, with Applications	2021-10-20	Paper
On non-optimally expanding sets in Grassmann graphs	2021-08-24	Paper
An Improved Dictatorship Test with Perfect Completeness	2020-11-25	Paper
The Andoni–Krauthgamer–Razenshteyn characterization of sketchable norms fails for sketchable metrics	2019-10-15	Paper
Towards a proof of the 2-to-1 games conjecture?	2019-08-22	Paper
On non-optimally expanding sets in Grassmann graphs	2019-08-22	Paper
Hardness of Finding Independent Sets in 2-Colorable and Almost 2-Colorable Hypergraphs	2019-06-20	Paper
On Monotonicity Testing and Boolean Isoperimetric-type Theorems	2018-12-19	Paper
An ~O(n) Queries Adaptive Tester for Unateness	2018-04-19	Paper
https://portal.mardi4nfdi.de/entity/Q4607982	2018-03-15	Paper
Hardness of Bipartite Expansion.	2018-03-02	Paper
https://portal.mardi4nfdi.de/entity/Q5371213	2017-10-25	Paper
Candidate hard unique game	2017-09-29	Paper
On independent sets, 2-to-2 games, and Grassmann graphs	2017-08-17	Paper
Towards an optimal query efficient PCP?	2017-05-16	Paper
A characterization of approximation resistance for even k-partite CSPs	2017-05-16	Paper
A Simple Deterministic Reduction for the Gap Minimum Distance of Code Problem	2017-05-16	Paper
Hardness of Coloring 2-Colorable 12-Uniform Hypergraphs with $2^{(\log {n})^{\Omega(1)}}$ Colors	2017-03-10	Paper
On Hardness of Approximating the Parameterized Clique Problem	2016-04-15	Paper
Approximating CSPs Using LP Relaxation	2015-10-27	Paper
The Unique Games Conjecture, Integrality Gap for Cut Problems and Embeddability of Negative-Type Metrics into ℓ 1	2015-08-14	Paper
A characterization of strong approximation resistance	2015-06-26	Paper
Integrality gaps for sparsest cut and minimum linear arrangement problems	2014-11-25	Paper
On earthmover distance, metric labeling, and 0-extension	2014-11-25	Paper
https://portal.mardi4nfdi.de/entity/Q3191598	2014-10-06	Paper
Almost Polynomial Factor Hardness for Closest Vector Problem with Preprocessing	2014-09-18	Paper
A Two Prover One Round Game with Strong Soundness	2014-07-30	Paper
Optimal Long Code Test with One Free Bit	2014-07-25	Paper
SDP Integrality Gaps with Local ell_1-Embeddability	2014-07-25	Paper
The Complexity of Somewhat Approximation Resistant Predicates	2014-07-01	Paper
NP-hardness of approximately solving linear equations over reals	2014-06-05	Paper
https://portal.mardi4nfdi.de/entity/Q5417658	2014-05-22	Paper
2 log1-ε n hardness for the closest vector problem with preprocessing	2014-05-13	Paper
$\mathcal{NP}$-Hardness of Approximately Solving Linear Equations over Reals	2013-09-25	Paper
Sharp kernel clustering algorithms and their associated Grothendieck inequalities	2013-05-28	Paper
Hardness of approximating the closest vector problem with pre-processing	2012-06-26	Paper
Grothendieck-Type Inequalities in Combinatorial Optimization	2012-06-25	Paper
https://portal.mardi4nfdi.de/entity/Q3096713	2011-11-11	Paper
A Simple Deterministic Reduction for the Gap Minimum Distance of Code Problem	2011-07-06	Paper
Combinatorial theorems about embedding trees on the real line	2011-06-07	Paper
https://portal.mardi4nfdi.de/entity/Q3002760	2011-05-24	Paper
https://portal.mardi4nfdi.de/entity/Q3002802	2011-05-24	Paper
https://portal.mardi4nfdi.de/entity/Q3002828	2011-05-24	Paper
On the hardness of learning intersections of two halfspaces	2011-01-18	Paper
Hardness of Reconstructing Multivariate Polynomials over Finite Fields	2011-01-17	Paper
Approximate Lasserre Integrality Gap for Unique Games	2010-09-10	Paper
Inapproximability of Hypergraph Vertex Cover and Applications to Scheduling Problems	2010-09-07	Paper
SDP Gaps for 2-to-1 and Other Label-Cover Variants	2010-09-07	Paper
A new multilayered PCP and the hardness of hypergraph vertex cover	2010-08-16	Paper
Cell-probe lower bounds for the partial match problem	2010-08-16	Paper
A new PCP outer verifier with applications to homogeneous linear equations and max-bisection	2010-08-15	Paper
Hardness results for approximate hypergraph coloring	2010-08-05	Paper
On the power of unique 2-prover 1-round games	2010-08-05	Paper
Fitting algebraic curves to noisy data	2010-08-05	Paper
On Earthmover Distance, Metric Labeling, and 0-Extension	2010-04-29	Paper
On Agnostic Learning of Parities, Monomials, and Halfspaces	2010-04-29	Paper
Inapproximability Results for Computational Problems on Lattices	2010-03-05	Paper
Approximate Kernel Clustering	2010-02-05	Paper
Linear Equations Modulo 2 and the $L_1$ Diameter of Convex Bodies	2009-08-20	Paper
Better Inapproximability Results for MaxClique, Chromatic Number and Min-3Lin-Deletion	2009-03-12	Paper
Approximation Algorithms for the Max-Min Allocation Problem	2009-02-17	Paper
Hardness of Embedding Metric Spaces of Equal Size	2009-02-17	Paper
https://portal.mardi4nfdi.de/entity/Q3549678	2009-01-05	Paper
https://portal.mardi4nfdi.de/entity/Q3549718	2009-01-05	Paper
Hardness of approximating the shortest vector problem in lattices	2008-12-21	Paper
Inapproximability results for combinatorial auctions with submodular utility functions	2008-09-12	Paper
Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?	2008-03-28	Paper
Vertex cover might be hard to approximate to within \(2 - \varepsilon \)	2008-03-11	Paper
Ruling Out PTAS for Graph Min‐Bisection, Dense k‐Subgraph, and Bipartite Clique	2007-09-07	Paper
Improved lower bounds on the randomized complexity of graph properties	2007-05-11	Paper
Nonembeddability theorems via Fourier analysis	2006-05-26	Paper
Hardness of approximating the shortest vector problem in high \(\ell_{p}\) norms	2006-04-28	Paper
A New Multilayered PCP and the Hardness of Hypergraph Vertex Cover	2005-09-16	Paper
Cell-probe lower bounds for the partial match problem	2004-11-18	Paper
Fitting algebraic curves to noisy data	2004-11-18	Paper
Parameterized complexity of finding subgraphs with hereditary properties.	2003-01-21	Paper
https://portal.mardi4nfdi.de/entity/Q2766822	2002-07-22	Paper
https://portal.mardi4nfdi.de/entity/Q4535024	2002-06-12	Paper
Evasiveness of Subgraph Containment and Related Properties	2002-04-23	Paper
https://portal.mardi4nfdi.de/entity/Q2762499	2002-01-09	Paper

Research outcomes over time

This page was built for person: Subhash A. Khot