516 citations · 2.7k across the 47 of their papers we have counts for
Showing 2013 · cs.CCShow all
2 papers · 2 filters
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★ 3 cited
Composition limits and separating examples for some Boolean function complexity measures
Justin Gilmer, Michael Saks, Srikanth Srinivasan
Block sensitivity (), certificate complexity () and fractional certificate complexity () are three fundamental combinatorial measures of complexity of a boolea…