Seminář z výpočetní složitosti

 Pavel Pudlák, Jiří Sgall

Michal Koucký (Rutgers, USA): Od univerzálních procházecích posloupností k objevným, aneb prostorova složitost s-t-spojitosti v neorientovaných grafech

Abstrakt: Univerzalni prochazeci a objevne posloupnosti (universal traversal and exploration sequences) jsou kombinatoricke objekty slouzici k navigaci pri prochazeni neorientovanym grafem. Jako takove nachazeji uplatneni pri zkoumani prostorove slozitosti s-t-spojitosti v neorientovanych grafech. V teto prednasce budeme definovat tyto posloupnosti, ukazeme jejich vzajemny vztah, explicitne sestrojime univerzalni objevne posloupnosti pro nektere specialni tridy grafu a zminime nektere zajimave experimentalni vysledky tykajici se jedne konkretni objevne posloupnosti.
Relevantni reference:
R. Aleliunas, R. Karp, R. Lipton, L. Lovasz, C. Rackoff: Random walks, universal traversal sequences and the complexity of maze problems, Proceedings of FOCS 20, pp. 218-223, 1979.
M. Koucky: Universal traversal sequences with backtracking, Proceedings of Conference on Computational Complexity, pp. 14-21, 2001.

Michael Sipser: Expanders, Randomness, or Time versus Space
(referuje Jirka Hanika)

Abstract: Let EH be the hypothesis that a certain type of expander graph has an explicit construction. Let io-SPACE(T(n)) be the class of problems solvable by algorithms that for infinitely many inputs use at most space T(n).  Then the following holds: There exists epsilon greater than 0 such that for any polynomial time bound T(n)=n^k, EH implies P=R or TIME(T(n)) is a subset of io-SPACE(T^(1-epsilon)(n)).

Omer Reingold, Salil Vadhan, Avi Wigderson: Entropy Waves, the Zig-Zag Graph Product, and New Constant-Degree Expanders and Extractors
ECCC Report TR01-018
(Referuje Daniel Kral')

Abstract:
The main contribution of this work is a new type of graph product, which we call the zig-zag product.  Taking a product of a large graph with a small graph, the resulting graph inherits (roughly) its size from the large one, its degree from the small one, and its expansion properties from both! Iteration yields simple explicit constructions of constant-degree expanders of every size, starting from one constant-size expander.

A variant of this product can be applied to extractors, giving the first explicit extractors whose seed length depends (poly)logarithmically on only the entropy deficiency of the source (rather than its length) and that extract almost all the entropy of high min-entropy sources. These high min-entropy extractors have several interesting applications, including the first constant-degree explicit expanders which beat the "eigenvalue bound".

Russell Impagliazzo, Ronen Shaltiel, Avi Wigderson: Extractors and pseudo-random generators with optimal seed length
ECCC Report TR00-009
(referuje Emil Jerabek)

Abstract:
We give the first construction of a pseudo-random generator with optimal seed length that uses (essentially) arbitrary hardness. It builds on the novel recursive use of the NW-generator in a previous paper by the same authors, which produced many optimal generators one of which was pseudo-random. This is achieved in two stages - first significantly reducing the number of candidate generators, and then efficiently combining them into one.

We also give the first construction of an extractor with optimal seed length, that can handle sub-polynomial entropy levels. It builds on the fundamental connection between extractors and pseudo-random generators discovered by Trevisan, combined with construction above. Moreover, using Kolmogorov Complexity rather than circuit size in the analysis gives super-polynomial savings for our construction, and renders our extractors better than known for all entropy levels.Článek uvádi konstrukci skoro optimálních extraktorů, které jsou v určitém smyslu optimální.

Luca Trevisan: Construction of Near-Optimal Extractors Using Pseudo-Random Generators
(referuje Martin Pergel)

Článek uvádi konstrukci skoro optimálních extraktorů, které jsou v určitém smyslu optimální.
Lze ho stáhnout jako ECCC Report TR98-055.

P. Pudlák: Expandery, dispersery a extraktory
Pokračování úvodní přednášky ze 16. 10.
Na tyto základy bude navazovat několik článků, které plánujeme referovat. A. V. Kostochka: A bound of the cardinality of families not containing Delta-systems
(referuje J. Sgall)

Další článek z extremální kombinatoriky. Volně navazuje na program z 9. 10.

P. Pudlák: Expandery, dispersery a extraktory
Zavedeme pojmy, dokážeme základní vlastnosti a souvislost s vlastními čísly.
Na tyto základy bude navazovat několik článků, které plánujeme referovat. On set systems without weak 3-Delta-subsystems
by Axenovich, Fon-Der-Flaass, Kostochka
Discrete Mathematics 138 (1995), 57-62
(referuje J. Sgall)

Clanek obsahuje vysledek z oblasti extremalni kombinatoriky, ktera volne souvisi s vypocetni slozitosti. Krome vlastniho vysledku strucne zopakujeme i aktualni stav problematiky a otevrene problemy.