11 citations · 27 across the 17 of their papers we have counts for
Showing 2013 · cs.CCShow all
3 papers · 2 filters
cs.CC2013
On the NP-Hardness of Approximating Ordering Constraint Satisfaction Problems
Per Austrin, Rajsekar Manokaran, Cenny Wenner
We show improved NP-hardness of approximating Ordering Constraint Satisfaction Problems (OCSPs). For the two most well-studied OCSPs, Maximum Acyclic Subgraph and Maximum Betweenne…
cs.CC2013
A Characterization of Approximation Resistance for Even -Partite CSPs
Per Austrin, Subhash Khot
A constraint satisfaction problem (CSP) is said to be \emph{approximation resistant} if it is hard to approximate better than the trivial algorithm which picks a uniformly random a…
cs.CC2013
On the Power of Many One-Bit Provers
Per Austrin, Johan Håstad, Rafael Pass
We study the class of languages, denoted by $\MIP[k, 1-ε, s]$, which have -prover games where each prover just sends a \emph{single} bit, with completeness and soundness e…