All reports by Author Pratik Worah:

__
TR13-146
| 20th October 2013
__

Subhash Khot, Madhur Tulsiani, Pratik Worah#### A Characterization of Approximation Resistance

Revisions: 1

__
TR13-075
| 23rd May 2013
__

Subhash Khot, Madhur Tulsiani, Pratik Worah#### A Characterization of Strong Approximation Resistance

__
TR13-017
| 23rd January 2013
__

Pratik Worah#### A Short Excursion into Semi-Algebraic Hierarchies

__
TR12-151
| 6th November 2012
__

Subhash Khot, Madhur Tulsiani, Pratik Worah#### The Complexity of Somewhat Approximation Resistant Predicates

Revisions: 1

__
TR12-105
| 17th August 2012
__

Madhur Tulsiani, Pratik Worah#### $LS_+$ Lower Bounds from Pairwise Independence

__
TR12-003
| 13th December 2011
__

Pratik Worah#### Rank Bounds for a Hierarchy of Lov\'{a}sz and Schrijver

Subhash Khot, Madhur Tulsiani, Pratik Worah

A predicate $f:\{-1,1\}^k \mapsto \{0,1\}$ with $\rho(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 $\rho(f)+\Omega(1)$ fraction of the constraints.

We present a complete characterization of approximation resistant predicates under the ... more >>>

Subhash Khot, Madhur Tulsiani, Pratik Worah

For a predicate $f:\{-1,1\}^k \mapsto \{0,1\}$ with $\rho(f) = \frac{|f^{-1}(1)|}{2^k}$, we call the predicate strongly approximation resistant if given a near-satisfiable instance of CSP$(f)$, it is computationally hard to find an assignment such that the fraction of constraints satisfied is outside the range $[\rho(f)-\Omega(1), \rho(f)+\Omega(1)]$.

We present a characterization of ... more >>>

Pratik Worah

This brief survey gives a (roughly) self-contained overview of some complexity theoretic results about semi-algebraic proof systems and related hierarchies and the strong connections between them. The article is not intended to be a detailed survey on "Lift and Project" type optimization hierarchies (cf. Chlamtac and Tulsiani) or related proof ... more >>>

Subhash Khot, Madhur Tulsiani, Pratik Worah

A boolean predicate $f:\{0,1\}^k\to\{0,1\}$ is said to be {\em somewhat approximation resistant} if for some constant $\tau > \frac{|f^{-1}(1)|}{2^k}$, given a $\tau$-satisfiable instance of the MAX-$k$-CSP$(f)$ problem, it is NP-hard to find an assignment that {\it strictly beats} the naive algorithm that outputs a uniformly random assignment. Let $\tau(f)$ denote ... more >>>

Madhur Tulsiani, Pratik Worah

We consider the complexity of LS$_+$ refutations of unsatisfiable instances of Constraint Satisfaction Problems (CSPs) when the underlying predicate supports a pairwise independent distribution on its satisfying assignments. This is the most general condition on the predicates under which the corresponding MAX-CSP problem is known to be approximation resistant.

We ... more >>>

Pratik Worah

Lov\'{a}sz and Schrijver introduced several lift and project methods for $0$-$1$ integer programs, now collectively known as Lov\'{a}sz-Schrijver ($LS$) hierarchies. Several lower bounds have since been proven for the rank of various linear programming relaxations in the $LS$ and $LS_+$ hierarchies. In this paper we investigate rank bounds in the ... more >>>