Suppose we are given an oracle that claims to approximate the permanent for most matrices $X$, where $X$ is chosen from the Gaussian ensemble (the matrix entries are i.i.d. univariate complex Gaussians). Can we test that the oracle satisfies this claim? This paper gives a polynomial-time algorithm for the task.

... more >>>

We prove that, assuming the Unique Games Conjecture (UGC), every problem in the class of ordering constraint satisfaction problems (OCSP) where each constraint has constant arity is approximation
resistant. In other words, we show that if $\rho$ is the expected fraction of constraints satisfied by a random ordering, then obtaining ... more >>>

In this paper we will be concerned with a large class of packing
and covering problems which includes Vertex Cover and Independent Set.
Typically, for NP-hard problems among them, one can write an LP relaxation and
then round the solution. For instance, for Vertex Cover, one can obtain a
more >>>