|
|
Close Help | ||||||||||||||
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.
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)).
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".
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í.
Č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.
Další článek z extremální kombinatoriky. Volně navazuje na program z 9. 10.
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.
