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.
Roman Smolensky: On Representations by Low-Degree Polynomials.
FOCS 1993: 130-138
(referuje Štěpán Kasal)
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í.
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.

M. Chrobak, J. Sgall: The weighted 2-server problem
(referuje J. Sgall)