Dear colleagues,

let me invite you to the doctoral seminar tomorrow (Thursday) at 9:50 in S6. I will present the paper

Subhash Khot and Dana Moshkovitz: NP-Hardness of Approximately Solving Linear Equations over Reals (presented at STOC 2011, published at Siam Journal of Computing 2013).

Abstract: 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 “nontrivial.” Here is an informal statement of our result: it is NP-hard to distinguish whether there is a nontrivial assignment that satisfies 1-delta fraction of the equations or every nontrivial assignment fails to satisfy a constant fraction of the equations with a “margin” of Omega(sqrt{delta}). We develop linearity and dictatorship testing procedures for functions f: R^n -> R over a Gaussian space, which could be of independent interest. Our research is motivated by a possible approach to proving the unique games conjecture.

---

At the doctoral seminar, we will see a "big picture" of the proof, followed by a discussion of the dictator test. As is common in PCP theory, some Fourier analysis will be present, but you should not worry about it.

If you miss the seminar, you can see prof. Moshkovitz talk about it here: https://www.youtube.com/watch?v=ER-UFGsyLVc

I would also like to point at the paper discussing the second step of the approach to proving the unique games conjecture:

Subhash Khot and Dana Moshkovitz: Candidate Hard Unique Game (STOC 2016) https://people.csail.mit.edu/dmoshkov/papers/ugc/candidate-linear.pdf

See you all there, Martin Böhm