85 citations · 294 across the 35 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★ 4 cited
A strong direct product theorem for the tribes function via the smooth-rectangle bound
Prahladh Harsha, Rahul Jain
The main result of this paper is an optimal strong direct product result for the two-party public-coin randomized communication complexity of the Tribes function. This is proved by…