## UNIVERSITY OF PENNSYLVANIA

## Department of Mathematics

Fall 2012 -Hans Rademacher Lectures in Mathematics

Avi Wigderson

## Institute for Advanced Study, Princeton

will speak on

## Computational Complexity and Mathematics

This series of talks is aimed at expositing certain research directions within computational complexity and some of their interaction with various branches of mathematics, including probability, group theory, geometry, analysis and algebra. The first three will survey large areas, while the last will be more focused.

The lectures are independent of each other, and no special background is assumes.

The power and weakness of randomness (when you are short on time)

Monday....November 5, 2012....4:30pm....A6 DRL

Abstract: 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 respectively its power and weakness for making algorithms faster. I will also address the role of randomness in other computational settings, such as space bounded computation and probabilistic and zero-knowledge proofs.

Arithmetic complexity

Tuesday....November 6, 2012....4:30pm....A6 DRL

Abstract: How fast can we compute the Fourier Transform, or solve a linear system? What are the shortest formulas for the Determinant and the Permanent? Arithmetic complexity studies the computation number of arithmetic operations, required to compute natural polynomials. I will survey basic questions, results and open problems in this area. I will also explain their connection to the P vs. NP question and to Quantum Mechanics.

Expander graphs - constructions and applications

Wednesday....November 7, 2012....4:30pm....A6 DRL

Abstract: Expanders are graphs (or networks) which are sparse but are extremely well connected. These objects are "pseudo-random" - look like random graphs from several viewpoints. And they are amongst the most useful mathematical objects: They play fundamental roles in solving computer science problems in error-correcting codes, data structure, cryptography, de-randomization and more, and mathematics problems in group theory, topology, geometry and more. Random graphs are expanders, but typically explicit constructions are needed. In this talk I will define expanders, discuss their construction and survey some of their applications.

Points, Lines and Codes

Thursday....November 8, 2012....4:30pm....A6 DRL

Abstract: A classical Sylvester-Gallai theorem in Euclidean geometry asserts that if a set of points in Real space has the property that every line through two of them contains a third point, then they must all be on the same line. Over the complex numbers such a set can span two dimensions, but not higher - Kelly's theorem asserts that they must all be on the same plane. I will describe several approximate and robust versions of these theorems (and related ones), in which the information given is only that certain triples are co-linear, or only about proximity to co-linearity. These questions are motivated from several areas, including locally correctable codes, arithmetic combinatorics and matrix rigidity. The proofs use an interesting combination of combinatorial, algebraic and analytic tools.

Lectures will be held in the David Rittenhouse Laboratory (DRL),

S.E. corner of 33rd and Walnut Streets, Philadelphia, PA.

Tea: 4E17 DRL at 4:00pm.

For further information, please call the Department of Mathematics at the University of Pennsylvania - 215-898-8627.