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]
- "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]