61 citations · 83 across the 10 of their papers we have counts for
Showing 2013Show all
2 papers · 1 filter
cs.CC2013★ 11 cited
Super-polylogarithmic hypergraph coloring hardness via low-degree long codes
Venkatesan Guruswami, Johan Hastad, Prahladh Harsha +2
We prove improved inapproximability results for hypergraph coloring using the low-degree polynomial code (aka, the 'short code' of Barak et. al. [FOCS 2012]) and the techniques pro…
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…