Seminář z výpočetní složitosti
Pavel Pudlák, Jiří Sgall
Předchozí program semináře, zimní semestr 2002 [Previous program, Fall
2002]
14. 1. 2003 (úterý [Tuesday], 10.15, MÚ Žitná 25, 1.
patro)
Michal Koucký: Síla ukrytá v náhodných řetízcích - Power from random strings
(joint work with Eric Allender, Harry Buhrman, Dieter van Melkebeek and Detlef Ronneburger)
Kolmogorov complexity is a measure of randomness contained in finite
strings. In the paper, we show that sets consisting of strings of high Kolmogorov
complexity provide examples of sets that are complete for several complexity
classes under probabilistic and non-uniform reductions. These sets are provably
not complete under the usual many-one reductions.
17. 12. 2002, 7. 1. 2003 (úterý [Tuesday], 10.15, MÚ Žitná 25, 1.
patro)
Valentine Kabanets, Russell Impagliazzo: Derandomizing Polynomial Identity
Tests Means Proving Circuit Lower Bounds.
Electronic Colloquium on Computational
Complexity (ECCC)(055): (2002)
(referuje Emil Jeřábek)
Článek studuje velmi zajímavé souvislosti mezi derandomizací a dokazováním dolních odhadů.
10. 12. 2002 (úterý [Tuesday], 10.15, MÚ Žitná 25, 1.
patro)
Gabor Tardos, David A. Mix Barrington: A Lower Bound on the Mod 6 Degree
of the Or Function.
Computational Complexity 7(2): 99-108 (1998)
(referuje Petr Kučera)
Článek dokazuje dolní odhad na reprezentaci OR polynomy modulo složené číslo,
dosud nejlepší i když značně vzdálený od horního odhadu z minulého semináře.
3. 12. 2002 (úterý [Tuesday], 10.15, MÚ Žitná 25, 1.
patro)
D. Barrington, R. Beigel, and S. Rudich. Representing Boolean Functions
as Polynomials Modulo Composite Integers,
Computational Complexity, 4:367-382, 1994. Special issue devoted to the 4th Annual McGill Workshop on
Complexity Theory. (Also in STOC '92.)
(referuje Petr Kučera)
Článek se zabývá reprezentací Booleovských funkcí polynomy modulo složené
číslo a dokazuje překvapivý horní odhad.
12. 11., 19. 11., 26. 11. 2002 (úterý [Tuesday], 10.15, MÚ Žitná 25, 1.
patro)
Roman Smolensky: On Representations by Low-Degree Polynomials.
FOCS 1993: 130-138
(referuje Štěpán Kasal)
22. 10., 5. 11. 2002 (úterý [Tuesday], 10.15, MÚ Žitná 25, 1.
patro)
Alan R. Woods:
Unsatisfiable Systems of Equations, Over a Finite Field.
in Proc. 39-th FOCS, IEEE Computer Society 1998, pp. 202-211
(referuje Pavel Pudlák)
Článek se zabývá splnitelností systému kvadratických rovnic. Dokazuje,
že pro nesplnitelný systém vždy existuje o něco kratší důkaz než probírání
všech ohodnocení.
29. 10. 2002 (úterý [Tuesday], 10.15, MÚ Žitná 25, 1.
patro)
V. Grolmusz: Low Rank Co-Diagonal Matrices and Ramsey Graphs
Electronic Journal of Combinatorics, Vol. 7, (2000), No. 1, R15
(referuje Daniel Král')
Článek se zabývá explicitní konstrukcí jistých Ramseyovských grafů, metoda
souvisí se studiem obvodů s hradly pro počítání modulo složené číslo.
15. 10. 2002 (úterý [Tuesday], 10.15, MÚ Žitná 25, 1.
patro)
M. Chrobak, J. Sgall: The weighted 2-server problem
(referuje J. Sgall)