Pseudorandomness in Mathematical Structures Program

All sessions will take place in Wolfensohn Hall.

Tutorials - Monday and Tuesday, June 14-15

Monday, June 14

9:00 am - 10:30 am, 11:00 am - 12:30 pm (coffee/tea break 10:30 am -11:00 am)
Ben Green, University of Cambridge (on leave at the Radcliffe Institute, Harvard 2009-2010)
Approximate algebraic structure (groups, fields, homomorphisms, ...)

12:30 pm - 2:00 pm Lunch

2:00 pm-3:30 pm, 4:00 pm - 5:30 pm (coffee/tea break at 3:30 pm)
Russell Impagliazzo, UC San Diego and Institute for Advanced Study
Computational pseudo-randomness and extractors

Tuesday, June 15

9:00 am - 10:30 am, 11:00 am - 12:00 pm (coffee/tea break 10:30 am - 11:00 am)
Avi Wigderson Institute for Advanced Study
Expander graphs: Applications and combinatorial constructions

12:00 pm - 1:00 pm Lunch (Please note: The Dining Hall will close at 1:00 p.m. for their staff to attend the IAS Staff picnic.)

2:00 pm - 3:30 pm, 4:00 pm - 5:30 pm (coffee/tea break at 3:30 pm)
Luca Trevisan, UC Berkeley
Regularity Lemmas in graph theory, additive combinatorics and TCS

*****************************************

Survey Lectures - Wednesday-Friday, June 16-18

Wednesday, June 16

9:30 am - 10:45 am Timothy Gowers, Cambridge University
Quasi-random groups

10:45 am - 11:15 am Coffee/tea break

11:15 am - 12:30 pm Fan Chung Graham, UC San Diego
Quasi-random graphs and hypergraphs

12:30 pm - 2:15 pm Lunch

2:15 pm - 3:30 pm Jean Bourgain, Institute for Advanced Study
Expansion in Lie groups and applications

3:30 pm - 4:00 pm Coffee/tea break

4:00 pm - 5:15 pm Benjamin Weiss, Einstein Institute of Math, Hebrew University
Random-like behavior in deterministic systems

Thursday, June 17

9:30 am - 10:45 am Jean Bourgain, Institute for Advanced Study
Group expansion and the affine sieve

10:45 am - 11:15 pm Coffee/tea break

11:15 am - 12:30 pm Ryan O'Donnell, Carnegie Mellon University
Quasi-random boolean functions, and inapproximability

12:30 pm - 2:15 pm Lunch

2:15 pm - 3:30 pm Alex Lubotzky, Einstein Institute of Mathematics, Hebrew University
Randomness in group theory

3:30 - 4:00 pm Coffee/tea break

4:00 - 5:15 pm Van Vu, Rutgers University
Random matrices and their spectra

Friday, June 18

9:30 am - 10:45 am Dimitris Achlioptas, UC Santa Cruz and RACTI, Greece
Structure of solutions to random constraint satisfaction problems

10:45 am - 11:15 am Coffee/tea break

11:15 am - 12:30 pm Tamar Ziegler, Technion - Israel Institute of Technology
An inverse theorem for the Gowers norms over finite fields

12:30 pm - 2:15 pm Lunch

2:15 pm - 3:30 pm Sergei Konyagin, Steklov Mathematical Institute
Pseudorandom matrices and explicit constructions related to sparse signal recovery

3:30 pm - 4:00 pm Coffee/tea break

4:00 pm - 5:15 pm Peter Sarnak, Princeton University and the Institute for Advanced Study
Pseudorandomness of the Mobius function

_____________________

The workshop is funded by the National Science Foundation grant DMS-0835373, "Pseudo-randomness in mathematics and computer science" and NSF grant CCF-0832797, Expeditions in Computing." The Workshop is co-sponsored by the Center for Computational Intractability at Princeton University.

Inquires should be addressed to: pseudo.workshop@gmail.com.