Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Dictatorship test:
TR10-112 | 15th July 2010
Subhash Khot, Dana Moshkovitz

NP-Hardness of Approximately Solving Linear Equations Over Reals

In this paper, we consider the problem of approximately solving a system of homogeneous linear equations over reals, where each
equation contains at most three variables.

Since the all-zero assignment always satisfies all the equations exactly, we restrict the assignments to be ``non-trivial". Here is
an informal statement of our ... more >>>

TR12-016 | 24th February 2012
Anindya De, Elchanan Mossel

Explicit Optimal hardness via Gaussian stability results

Revisions: 3

The results of Raghavendra (2008) show that assuming Khot's Unique Games Conjecture (2002), for every constraint satisfaction problem there exists a generic semi-definite program that achieves the optimal approximation factor. This result is existential as it does not provide an explicit optimal rounding procedure nor does it allow to calculate ... more >>>

ISSN 1433-8092 | Imprint