## Proving weak approximability without algorithms.

by Ridwan Syed and Madhur Tulsiani

#### Oded's comments

A nice reminder that feasibility results can be obtained non-explicitly;
here, by showing that a necessary condition for hardness is violated.

#### The original abstract

A boolean predicate is said to be strongly approximation resistant if,
given a near-satisfiable instance of its maximum constraint satisfaction
problem, it is hard to find an assignment such that the fraction of
constraints satisfied deviates significantly from the expected fraction of
constraints satisfied by a random assignment. A predicate which is not
strongly approximation resistant is known as weakly approximable.

We give a new method for proving the weak approximability of predicates,
using a simple SDP relaxation, without designing and analyzing new rounding
algorithms for each predicate. Instead, we use the recent characterization
of strong approximation resistance by Khot et al. [STOC 2014], and show how
to prove that for a given predicate, certain necessary conditions for
strong resistance derived from their characterization, are violated. By
their result, this implies the existence of a good rounding algorithm,
proving weak approximability.

We show how this method can be used to obtain simple proofs of (weak
approximability analogues of) various known results on approximability, as
well as new results on weak approximability of symmetric predicates

See Approx'16 proceedings version.

Back to
list of Oded's choices.