20092010 Seminars
Tuesday, May 25, 2010  The Stepanov Method Avi Wigderson (Professor, School of Mathemtics) video 
Monday, May 24, 2010  Subsampling Mathematical Relaxations and Averagecase Complexity Boaz Barak (Princeton University) video 
Tuesday, May 18, 2010  Reductions Between Expansion Problems Madhur Tulsiani (Member, School of Mathematics) video 
Tuesday, May 11, 2010  SmallBias Sets Amir Yehudayoff (Member, School of Mathematics) video 
Tuesday, May 4, 2010  Explicit Construction of RIP Matrices, Matrices With Small Coherence, and Related Problems Sergei Konyagin (Moscow State University and Member, School of Mathemtics) 
Tuesday, April 27, 2010  Hardness of Approximately Solving Linear Equations Over Reals Dana Moshkovitz (Member, School of Mathemtics) video 
Tuesday, April 20, 2010  Matching Vector Codes Zeev Dvir (Member, School of Mathemtics) 
Monday, April 19, 2010  Can Complexity Theory Ratify the Invisible Hand of the Market? Vijay Vazirani (Georgia Institute of Technology) video 
Tuesday, April 13, 2010  Critical Slowdown for the Ising Model on the TwoDimensional Lattice Eyal Lubetzky (Microsoft Research Redmond) video 
Monday, April 12, 2010  Cover Times, Blanket Times, and Majorizing Measures James Lee (University of Washington) video 
Tuesday, April 6, 2010  Mobius Randomness and Dynamics
Peter Sarnak (Professor, School of Mathematics) video 
Monday, April 5, 2010  Compressing BoundedRound Communication Mark Braverman (Microsoft Research New England) video 
Tuesday, March 30, 2010  A Combinatorial Proof of the ChernoffHoeffding Bound, With Applications to DirectProduct Theorems Valentine Kabanets (Simon Fraser University and Member, School of Mathematics) video 
Monday, March 29, 2010  COMPUTER SCIENCE/DISCRETE MATH I
There will be no TCS/DM Seminar talk today 
Tuesday, March 23, 2010  COMPUTER SCIENCE/DISCRETE MATH II
No talk today in lieu of the U.S. Income Tax Seminar for Members () 
Monday, March 22, 2010  Product Rules in Semidefinite Programming Rajat Mittal (Rutgers, The State Unviersity of New Jersey) video 
Tuesday, March 16, 2010  Pseudorandom Generators for Regular Branching Programs Amir Yehudayoff (Member, School of Mathematics) video 
Monday, March 15, 2010  Extremal Problems for Convex Lattice Polytopes Imre Barany (Alfred Renyi Mathematical Institute, Hungarian Academy of Sciences) video 
Tuesday, March 9, 2010  Algorithms vs. Hardness Nisheeth Vishnoi (Microsoft Research India) 
Monday, March 8, 2010  Behavioral Experiments in Strategic Networks Michael Kearns (University of Pennsylvania) video 
Tuesday, March 2, 2010  Computational Complexity and Information Asymmetry in Financial Products Boaz Barak (Princeton University) video 
Monday, March 1, 2010  A Theory of Cryptographic Complexity Manoj M. Prabhakaran (University of Illinois at UrbanaChampaign) video 
Tuesday, February 23, 2010  Testing Correlations and Inverse Theorems Hamed Hatami (Princeton University and Member, School of Mathematics) video 
Monday, February 22, 2010  Average Sensitivity of Polynomial Threshold Functions Rocco Servedio (Columbia University) video 
Tuesday, February 16, 2010  Complexity of Constraint Satisfaction problems: Exact and Approximate Prasad Raghavendra (University of Washington) video 
Monday, February 15, 2010  Graph Expansion and the Unique Games Conjecture David Steurer (Princeton University) 
Tuesday, February 9, 2010  Representation Theory and Expansion in Groups Avi Wigderson (Professor, School of Mathematics) video 
Monday, February 8, 2010  Interpreting Polynomial Structure Analytically Julia Wolf (Rutgers, The State University of New Jersey) video 
Tuesday, February 2, 2010  Representation Theory and Expansion in Groups Avi Wigderson (Professor, School of Mathematics) video 
Monday, February 1, 2010  A New Approach to the Inverse LittlewoodOfford Problem Hoi H. Nguyen (Rutgers, The State University) video 
Tuesday, January 26, 2010  Representation Theory and Expansion in Groups Avi Wigderson (Professor, School of Mathematics) video 
Monday, January 25, 2010  Expanders and CommunicationAvoiding Algorithms Oded Schwartz (Technical University Berlin) video 
Tuesday, January 19, 2010  Limits of Randomly Grown Graph Sequences Katalin Vesztergombi (Eotvos Lorand University, Budapest, Hungary) 
Tuesday, December 22, 2009  COMPUTER SCIENCE/DISCRETE MATH II
The talks will resume during the School of Mathematics Second Term. 
Monday, December 21, 2009  COMPUTER SCIENCE/DISCRETE MATH I
The talks will resume during the School of Mathematics Second Term. 
Tuesday, December 15, 2009  An Algorithmic Proof of Forster's Lower Bound Moritz Hardt (Princeton University) video 
Monday, December 14, 2009  A Parallel Repetition Theorem for Any Interactive Argument Iftach Ilan Haitner (Microsoft Research New England) video 
Tuesday, December 8, 2009  Algorithmic Dense Model Theorems, Decompositions, and Regularity Theorems Russell Impagliazzo (University of California at San Diego and Member, School of Mathematics) video 
Monday, December 7, 2009  The NOF Communication Complexity of Multiparty Pointer Jumping Joshua Brody (Dartmouth College) video 
Tuesday, December 1, 2009  Algorithmic Dense Model Theorems, Decompositions, and Regularity Theorems Russell Impagliazzo (University of California at San Diego and Member, School of Mathematics) 
Monday, November 30, 2009  COMPUTER SCIENCE/DISCRETE MATH I
There will be no talk today due to trave times from the Thanksgiving Holiday. 
Tuesday, November 24, 2009  Arithmetic Progressions in Primes Madhur Tulsiani (Member, School of Mathematics) video 
Monday, November 23, 2009  Privacy of Dynamic Data: Continual Observation and Pan Privacy Moni Naor (The Weizmann Institute of Science) video 
Tuesday, November 17, 2009  No Seminar  Oberwolfach Meeting on Complexity Theory

Monday, November 16, 2009  No Seminar  Oberwolfach Meeting on Complexity Theory

Tuesday, November 10, 2009  Graph and Subgraph Sparsification and its Implications to Linear System Solving and Transforming Graphs into Expanders Alexandra Kolla (Member, School of Mathematics) video 
Monday, November 9, 2009  Why Sex? Adi Livnat (University of California, Berkeley) 
Tuesday, November 3, 2009  Constructions of Expanders Using Group Theory Martin Kassabov (Cornell University and von Neumann Fellow, School of Mathematics) video 
Monday, November 2, 2009  Grothendieck Inequalities, XOR Games, and Communication Complexity Troy Lee (Rutgers, The State University of New Jersey) video 
Tuesday, October 27, 2009  <a href="http://www.cc.gatech.edu/focs2009/">http://www.cc.gatech.edu/focs2009/</a>
No Seminar Due to FOCS 2009 Symposium 
Monday, October 26, 2009  <a href="http://www.cc.gatech.edu/focs2009/">http://www.cc.gatech.edu/focs2009/</a>
No Seminar Due to FOCS 2009 Symposium 
Tuesday, October 20, 2009  Hardness of Projection Games Dana Moshkovitz (Member, School of Mathematics) video 
Monday, October 19, 2009  PCPs of SubConstant Error Via Derandomized Direct Product Or Meir (The Weizmann Institute of Science) video 
Tuesday, October 13, 2009  Using Local Conductance to Give Improved Algorithms for Unique Games William Matthews (University of California at San Diego) video 
Monday, October 12, 2009  On The Complexity of Circuit Satisfiability Ramamohan Paturi (University of California at San Diego) video 
Tuesday, October 6, 2009  The Completeness of the Permanent Amir Yehudayoff (Member, School of Mathematics) video 
Monday, October 5, 2009  The Detectability Lemma and Quantum Gap Amplification Itai Arad (Hebrew University of Jerusalem) video 
Tuesday, September 29, 2009  Span Programs and Quantum Query Algorithms Ben Reichardt (University of Waterloo, Canada) video 
Monday, September 28, 2009  COMPUTER SCIENCE/DISCRETE MATH I
No Seminar Today in Observance of Yom Kippur 
Tuesday, September 22, 2009  The Completeness of the Permanent Amir Yehudayoff (Member, School of Mathematics) video 
Monday, September 21, 2009  TwiceRamanujan Sparsifiers Nikhil Srivastava (Yale University) video 
Tuesday, September 15, 2009  Affine Dispersers from Subspace Polynomials Swastik Kopparty (Massachusetts Institute of Technology) video 
Monday, September 14, 2009  Blackbox Polynomial Identity Testing for Depth 3 Circuits Shubhangi Saraf (Massachusetts Institute of Technology) 