Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Moses Charikar:

TR11-027 | 28th February 2011
Venkatesan Guruswami, Johan HÃ¥stad, Rajsekar Manokaran, Prasad Raghavendra, Moses Charikar

Beating the Random Ordering is Hard: Every ordering CSP is approximation resistant

We prove that, assuming the Unique Games Conjecture (UGC), every problem in the class of ordering constraint satisfaction problems (OCSP) where each constraint has constant arity is approximation
resistant. In other words, we show that if $\rho$ is the expected fraction of constraints satisfied by a random ordering, then obtaining ... more >>>

ISSN 1433-8092 | Imprint