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, Hebrew University
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.