Survey Talks

Louis Clark Vanuxem Lectures - "A world view through the computational lens," three talks given at Princeton University (co-sponsored by Princeton University Press) - February 13, 14 and 15, 2007
[Abstract]
- Lecture I: "Algorithms: a common language for nature, man and computer"
  [PowerPoint] | 56k | 350k 56k | 250k
- Lecture II: "Time, space and the cosmology of computational problems"
  [PowerPoint] | 56k | 350k 56k | 350k
- Lecture III: "Cryptography: secrets and lies, knowledge and trust"
  [PowerPoint] | 56k | 350k 56k | 350k
"Kurt Gödel and Computer Science," a talk given at the Goedel Centenary at the IAS - November 17, 2006
[Abstract] | [Mpeg]
"Kurt Gödel, von Neumann, and Theoretical Computer Science"
a talk given at the 75th anniversary of the School of Mathematics at the IAS.
[Powerpoint] [RealVideo]
"Randomness Extractors - Applications and Constructions"
[PowerPoint]
"The power and weakness of randomness (when you are short on time)"
[PowerPoint] | [Abstract]
"Games computers (and computer scientists) play"
[PowerPoint]
"The digital envelope - a crash course in modern cryptography"
[PowerPoint]
"Depth through breadth (or why should we listen to talks in other areas)
[PowerPoint]
"Complexity insights"
[PowerPoint]
"Zigzag product, expander constructions, connections and applications" (more applications than the survey below)
[PowerPoint]
"Expander graphs - where combinatorics and algebra compete and cooperate" (more algebraic than the survey above)
[PowerPoint] | [Abstract]
"The art of reduction"
[PowerPoint] | [Abstract] Keynote lecture at FCRC, San Diego, CA - June 13, 2007
"Proof, Computation and Randomness"
[PowerPoint] | [Abstract] at National Science Foundation, Arlington, VA - September 27, 2007.
"The sum-product theorem and applications"
[Powerpoint] | [Abstract]
"The PvsNP Problem"
[PowerPoint] [Abstract] Public Lecture at the Institute for Advanced Study - October 24, 2008
"The Art of Reduction (or Depth through Breadth)"
Distinguished Lecturer Series at Penn State University, State College, PA - November 19, 2008
[PowerPoint] [Abstract]
"Randomness -- A computational complexity view"
Logic Seminar at Penn State University, State College, PA - November 20, 2008
[PowerPoint]
"Algebrization: A New Barrier in Complexity Theory"
Theory Seminar, CS Department, UC Berkeley - November 5, 2008
[PowerPoint]
"Seeded Randomness Extractors: applications and constructions"
Princeton University Discrete Math Seminar - February 19, 2009
[PowerPoint]
"Direct-product testing, and a new 2-query PCP"
Theory Seminar, CS Department, Technion - Israel Institute of Technology,
Haifa, Israel - March 1, 2009
[PowerPoint]
"Les Valiant's Permanent Gift to Theoretical Computer Science"
60th Birthday Celebration, Bethesda, MD - May 30, 2009
[PowerPoint]
"Theoretical Computer Science Methods in Asymptotic Geometry"
Vitali Milman's 70th Birthday Celebration, Tel Aviv, Israel - June 24, 2009
[PowerPoint]
"Quarter-century of proofs of the XOR lemma" (skeleton of a lecture)
[PowerPoint]
"Direct product testing, parallel repetition and foams
Analytical Methods in Combinatorics, Additive Number Theory and Computer Science Workshop, IPAM, UCLA - December 1-4, 2009
[PowerPoint]
"Expanders, Groups and Representations"
Laci Babai's 60th Birthday Celebration, Columbus, OH - March 21-25, 2010
[PowerPoint]
"Expander graphs - applications and combinatorial constructions"
A 3-hour tutorial, Pseudorandomness in Mathematical Structures Workshop, IAS, Princeton, NJ - June 14-18, 2010
[PowerPoint]
Endre Szemeredi and TCS
Endre Szemeredi's 70th Birthday Celebration, Budapest, Hungary - August 2-7, 2010
[PowerPoint]