Dear colleagues,
let me invite you to the doctoral seminar on this Thursday
at 9:50 in S6. Tomáš Masařík will present a paper:
Michael Lampis:
Model checking lower bounds for simple graphs [1]
With best regards,
Honza
[1] https://arxiv.org/abs/1302.4266
Dear colleagues,
the first doctoral seminar of the winter semester will take place this
Thursday 6 Oct at 10:40 in S6. We will present newly proposed papers and
create a preliminary schedule of the talks. The regular seminar will then
take place as usual, every Thursday at 9:50 (note the earlier time) in S6.
We are currently looking for volunteer speakers for Oct 13 and Oct 20. If
you are able to present at this date, please let us know. A selection of
papers can be found at http://kam.mff.cuni.cz/dokt_seminar/nabidka.html
(more will come tonight).
You will find the schedule and more information at
http://kam.mff.cuni.cz/dokt_seminar/
Looking forward to meeting you,
Robert
Dear colleagues,
doctoral seminar will take place tomorrow at 10:40 in room S6. Note the unusual
beginning. Tomorrow will not be any presentation, just selection of the offered
papers.
Best regards,
Honza Musilek
Dear colleagues,
let me invite you to the doctoral seminar on this Thursday
at 9:50 in S6. Radek Hušek will present a paper:
Yevgeniy Dodis, Mihai Patrascu, Mikkel Thorup:
Changing base without losing space [1]
With best regards,
Honza
[1] http://dl.acm.org/citation.cfm?id=1806771
Dear colleagues,
let me invite you to the doctoral seminar on this Thursday
at 9:50 in S6. Vojtěch Kaluža will present a paper:
F. Foucaud, M. Krivelevich, G. Perarnau:
Large subgraphs without short cycles [1]
With best regards,
Honza
[1] http://arxiv.org/abs/1401.4928
Dear colleagues,
let me invite you to the doctoral seminar on this Thursday
at 9:50 in S6. Martin Balko will present a paper:
Tomáš Kaiser, Matěj Stehlík:
Colouring quadrangulations of projective spaces [1]
With best regards,
Honza
[1] http://arxiv.org/abs/1310.5875
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