Avi Wigderson Lectures at IU

Avi Wigderson, an award-winning Israeli mathematician and computer scientist, gave the following three invited talks as part of a distinguished lectures series in the IU Department of Mathematics September 27, 28, and 29, 2006:

The Power and Weakness of Randomness in Computation

Abstract:

Man has grappled with the meaning and utility of randomness for centuries. Research in the Theory of Computation in the last 30 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 "pseudorandom" 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. 

The Sum-Product Theorem and Its Applications

Abstract:

How "orthogonal" are the basic field operations "+" and "x"? About two years ago, Bourgain, Katz, and Tao proved the following theorem (stated very informally). In every finite field, a set that does not grow much when we {em add} all pairs of elements, and when we {em multiply} all pairs of elements, must be very close to a subfield. In particular, prime fields have no such subsets! This theorem revealed its fundamental nature quickly. Shortly afterwards it has found many diverse applications, including in Number Theory, Group Theory, Combinatorial Geometry, and the explicit construction of Randomness Extractors and Ramsey Graphs. In this talk, I plan to explain some of the applications, and to sketch the main ideas of the proof of the sum-product theorem.

Expander Graphs: Constructions and Applications

Abstract:

Expander graphs are extremely useful objects. In computer science, their applications include 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 explicitly 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.