67 KAM Mathematical Colloquium
Avi Wigderson
(IAS, Princeton)
THE POWER AND WEAKNESS OF RANDOMNESS IN COMPUTATION
patek 27. dubna 2007 v 11:00, refektar, prvni patro - z duvodu oslav centra DIMATIA zaujmete prosim misto do 10:30.
Malostranske nam. 25, Praha 1
O den drive, ve ctvrtek 26. 4. 2007 v poslucharne S5 v 15:45 prednese A. Wigderson druhou prednasku Expander Graphs - Constructions and Applications.
Abstract I.
Man has grappled with the meaning and utility of randomness for centuries. Research in the Theory of Computation in the last thirty years has enriched this study considerably. I'll describe two main aspects of this research on randomness, demonstrating its power and weakness respectively.
Randomness is paramount to computational efficiency:
The use of randomness can dramatically enhance computation (and do other wonders) for a variety of problems and settings. In particular, examples will be given of probabilistic algorithms (with tiny error) for natural tasks in different areas of mathematics, which are exponentially faster than their (best known) deterministic counterparts.
Computational efficiency is paramount to understanding randomness:
I will explain the computationally-motivated definition of ``pseudrandom'' distributions, namely ones which cannot be distinguished from the uniform distribution by any efficient procedure from a given class. We then show how such pseudorandomness may be generated deterministically, from (appropriate) computationally difficult problems. Consequently, randomness is probably not as powerful as it seems above.
I'll conclude with the power of randomness in other computational settings, primarily probabilistic proof systems. We discuss the remarkable properties of zero-knowledge proofs and of probabilistically checkable proofs.
Abstract II.
Expander graphs are extremely useful objects. In computer science, their applications range from network design, computational complexity, derandomization, error correction, data organization and more. In mathematics they are used in topology, group theory, game theory, information theory and naturally, graph theory.
I plan to explain what expanders are, their basic properties, and survey
the quest to explicitely construct them. I'll focus on the
recent combinatorial constructions, via the ``zig-zag'' product,
and how these can go beyond the bounds achieved by algebraic methods.
I'll also demonstrate some of the applications.
O přednášejícím
Avi Wigderson studoval informatiku na Technionu (Izrael) a na Univerzite v Princetonu (USA). Jeho vyzkum zahrnuje vetsinu teoreticke informatiky a zasahuje podstatne do matematiky, hlavne kombinatoriky a optimalizace. V minulosti hostoval a byl zamestnan na prednich informatickych institucich (Berkeley, Jeruzalem, Princeton) a od roku 1999 je profesorem Instute for Advanced Study v Princetonu. Bez nadsazky lze tvrdit, ze prof. Wigderson je jednim z nejznamejsich a nejvlivnejsich informatiku dneska. To je mozne dolozit nejenom rozsahem jeho vedecke prace (pres 160 publikaci), mnozstvim a kvalitou studentu, ale i tim, ze prednesl zvanou prednasku na trech Mezinarodnich kongresech matematiku (Kjoto 1990, Curych 1994, Madrid 2006). V roce 1994 mu byla na kongresu v Curychu udelena Nevanlinnova cena. Avi prednese v Praze dve prednasky urcene siroke matematicke a informaticke verejnosti. Prednaska 26. dubna je venovana oblasti jeho dlouhodobeho zajmu, expanderovym grafum, ktere maji mnoho aplikaci (viz napr. Bulletin AMS 43,4 (2006), 439 - 561). Jeho prazske kolokvium 27. dubna je venovano problemu P versus NP v kontextu soucasne matematiky a informatiky, a jeho zakladem je plenarni prednaska, kterou prednesl v r. 2006 na madridskem kongresu.
