2009-2010 Seminars

Tuesday, May 25, 2010
The Stepanov Method
Avi Wigderson (Professor, School of Mathemtics)
video
Monday, May 24, 2010
Subsampling Mathematical Relaxations and Average-case 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
Small-Bias 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 Two-Dimensional 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 Bounded-Round Communication
Mark Braverman (Microsoft Research New England)
video
Tuesday, March 30, 2010
A Combinatorial Proof of the Chernoff-Hoeffding Bound, With Applications to Direct-Product 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 Urbana-Champaign)
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 Littlewood-Offord 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 Communication-Avoiding 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 Sub-Constant 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
Twice-Ramanujan 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)