Dear colleagues,
let me invite you to the doctoral seminar on this Thursday
at 9:50 in S6. Jana Syrovátková will present a paper:
Ayush Choure, Sundar Vishwanathan:
Random walks, electric networks and the transience class problem of sandpiles [1]
With best regards,
Honza
[1] http://arxiv.org/abs/1105.3368
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
Dear colleagues,
let me invite you to the doctoral seminar on this Thursday
at 9:50 in S6. Jaroslav Hančl will present a paper:
Brendan Murphy, Oliver Roche-Newton, Ilya Shkredov:
Variations on the sum-product problem [1]
With best regards,
Honza
[1] http://arxiv.org/abs/1312.6438