Expanders and Extractors

Workshop | January 30 – February 3, 2017 every day |  Calvin Laboratory (Simons Institute for the Theory of Computing)

 Simons Institute for the Theory of Computing

This workshop will focus on explicit constructions of graphs and functions with pseudorandom properties. There will be two main themes related to each object in the title. For expanders, these will be proofs of existence of expander graphs using lifts, a la Bilu-Linial and Marcus-Spielman-Srivastava, and the possibility of using the method to obtain explicit constructions of Ramanujan expanders of all degrees; and constructions of Cayley expanders and the group-theoretic results motivated by such results. For randomness extractors, these will be constructions of extractors for independent sources and their applications to the construction of Ramsey graphs and other objects; and constructions of extractors in other settings and their applications to pseudorandom generators, coding theory, cryptography and other areas of computer science.

Noga Alon (Tel Aviv University; chair), Ben Green (University of Oxford), Peter Sarnak (Princeton University), David Zuckerman (University of Texas, Austin).

  Register online

 simonsevents@berkeley.edu, 510-664-9856