BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Subhash Khot

Subhash Khot appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
Computational ComplexityData Structures and Algorithmsmath.COmath.FA

Catalog footprint

What is connected

9works
4topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

9 published item(s)

preprint2020arXiv

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

A seminal result of Håstad [J. ACM, 48(4):798--859, 2001] shows that it is NP-hard to find an assignment that satisfies $\frac{1}{|G|}+\varepsilon$ fraction of the constraints of a given $k$-LIN instance over an abelian group, even if there is an assignment that satisfies $(1-\varepsilon)$ fraction of the constraints, for any constant $\varepsilon>0$. Engebretsen et al. [Theoretical Computer Science, 312(1):17--45, 2004] later showed that the same hardness result holds for $k$-LIN instances over any finite non-abelian group. Unlike the abelian case, where we can efficiently find a solution if the instance is satisfiable, in the non-abelian case, it is NP-complete to decide if a given system of linear equations is satisfiable or not, as shown by Goldmann and Russell [Information and Computation, 178(1):253--262. 2002]. Surprisingly, for certain non-abelian groups $G$, given a satisfiable $k$-LIN instance over $G$, one can in fact do better than just outputting a random assignment using a simple but clever algorithm. The approximation factor achieved by this algorithm varies with the underlying group. In this paper, we show that this algorithm is {\em optimal} by proving a tight hardness of approximation of satisfiable $k$-LIN instance over {\em any} non-abelian $G$, assuming $P \neq NP$. As a corollary, we also get $3$-query probabilistically checkable proofs with perfect completeness over large alphabets with improved soundness.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

A Characterization of Approximation Resistance

A predicate f:{-1,1}^k -> {0,1} with ρ(f) = \frac{|f^{-1}(1)|}{2^k} is called {\it approximation resistant} if given a near-satisfiable instance of CSP(f), it is computationally hard to find an assignment that satisfies at least ρ(f)+Ω(1) fraction of the constraints. We present a complete characterization of approximation resistant predicates under the Unique Games Conjecture. We also present characterizations in the {\it mixed} linear and semi-definite programming hierarchy and the Sherali-Adams linear programming hierarchy. In the former case, the characterization coincides with the one based on UGC. Each of the two characterizations is in terms of existence of a probability measure with certain symmetry properties on a natural convex polytope associated with the predicate.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

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

This work studies the hardness of finding independent sets in hypergraphs which are either 2-colorable or are almost 2-colorable, i.e. can be 2-colored after removing a small fraction of vertices and the incident hyperedges. To be precise, say that a hypergraph is (1-eps)-almost 2-colorable if removing an eps fraction of its vertices and all hyperedges incident on them makes the remaining hypergraph 2-colorable. In particular we prove the following results. For an arbitrarily small constant gamma > 0, there is a constant xi > 0, such that, given a 4-uniform hypergraph on n vertices which is (1 - eps)-almost 2-colorable for eps = 2^{-(log n)^xi}, it is quasi-NP-hard to find an independent set of n/(2^{(log n)^{1-gamma}}) vertices. For any constants eps, delta > 0, given as input a 3-uniform hypergraph on $n$ vertices which is (1-eps)-almost 2-colorable, it is NP-hard to find an independent set of delta n vertices. Assuming the d-to-1 Games Conjecture the following holds. For any constant delta > 0, given a 2-colorable 3-uniform hypergraph on n vertices, it is NP-hard to find an independent set of delta n vertices. The hardness result on independent set in almost 2-colorable 3-uniform hypergraphs was earlier known only assuming the Unique Games Conjecture. In this work we prove the result unconditionally. For independent sets in 2-colorable 3-uniform hypergaphs we prove the first strong hardness result, albeit assuming the d-to-1 Games Conjecture. Our result on almost 2-colorable 4-uniform hypergraphs gives the first nearly polynomial hardness factor for independent set in hypergraphs which are (almost) colorable with constantly many colors. It partially bridges the gap between the previous best lower bound of poly(log n) and the algorithmic upper bounds of n^{Omega(1)}.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

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

We prove that for an arbitrarily small constant $\eps>0,$ assuming NP$\not \subseteq$DTIME$(2^{{\log^{O(1/\eps)} n}})$, the preprocessing versions of the closest vector problem and the nearest codeword problem are hard to approximate within a factor better than $2^{\log ^{1-\eps}n}.$ This improves upon the previous hardness factor of $(\log n)^δ$ for some $δ> 0$ due to \cite{AKKV05}.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

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

We present a simple deterministic gap-preserving reduction from SAT to the Minimum Distance of Code Problem over $\F_2$. We also show how to extend the reduction to work over any finite field. Previously a randomized reduction was known due to Dumer, Micciancio, and Sudan, which was recently derandomized by Cheng and Wan. These reductions rely on highly non-trivial coding theoretic constructions whereas our reduction is elementary. As an additional feature, our reduction gives a constant factor hardness even for asymptotically good codes, i.e., having constant rate and relative distance. Previously it was not known how to achieve deterministic reductions for such codes.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

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

These are the lecture notes for the DIMACS Tutorial "Limits of Approximation Algorithms: PCPs and Unique Games" held at the DIMACS Center, CoRE Building, Rutgers University on 20-21 July, 2009. This tutorial was jointly sponsored by the DIMACS Special Focus on Hardness of Approximation, the DIMACS Special Focus on Algorithmic Foundations of the Internet, and the Center for Computational Intractability with support from the National Security Agency and the National Science Foundation. The speakers at the tutorial were Matthew Andrews, Sanjeev Arora, Moses Charikar, Prahladh Harsha, Subhash Khot, Dana Moshkovitz and Lisa Zhang. The sribes were Ashkan Aazami, Dev Desai, Igor Gorodezky, Geetha Jagannathan, Alexander S. Kulikov, Darakhshan J. Mir, Alantha Newman, Aleksandar Nikolov, David Pritchard and Gwen Spencer.

0 citations0 reviewsNo code linkedOpen access