Tight Bounds on the Approximability of Almost-satisfiable Horn SAT and Exact Hitting Set.

Venkatesan Guruswami, Yuan Zhou

Browse the full SODA paper archive.