2009-2010 Seminars

Monday, March 15, 2010 Imre Barany , Alfred Renyi Mathematical Institute, Hungarian Academy of Sciences
Extremal Problems for Convex Lattice Polytopes
Tuesday, March 9, 2010 Nisheeth Vishnoi , Microsoft Research India
Algorithms vs. Hardness
Monday, March 8, 2010 Michael Kearns , University of Pennsylvania
Behavioral Experiments in Strategic Networks		 video
Tuesday, March 2, 2010 Boaz Barak , Princeton University
Computational Complexity and Information Asymmetry in Financial Products		 video
Monday, March 1, 2010 Manoj M. Prabhakaran , University of Illinois at Urbana-Champaign
A Theory of Cryptographic Complexity		 video
Tuesday, February 23, 2010 Hamed Hatami , Princeton University; Member, School of Mathematics
Testing Correlations and Inverse Theorems		 video
Monday, February 22, 2010 Rocco Servedio , Columbia University
Average Sensitivity of Polynomial Threshold Functions		 video
Tuesday, February 16, 2010 Prasad Raghavendra , University of Washington
Complexity of Constraint Satisfaction problems: Exact and Approximate		 video
Monday, February 15, 2010 David Steurer , Princeton University
Graph Expansion and the Unique Games Conjecture
Tuesday, February 9, 2010 Avi Wigderson , Professor, School of Mathematics
Representation Theory and Expansion in Groups		 video
Monday, February 8, 2010 Julia Wolf , Rutgers, The State University of New Jersey
Interpreting Polynomial Structure Analytically		 video
Tuesday, February 2, 2010 Avi Wigderson , Professor, School of Mathematics
Representation Theory and Expansion in Groups		 video
Monday, February 1, 2010 Hoi H. Nguyen , Rutgers, The State University
A New Approach to the Inverse Littlewood-Offord Problem		 video
Tuesday, January 26, 2010 Avi Wigderson , Professor, School of Mathematics
Representation Theory and Expansion in Groups		 video
Monday, January 25, 2010 Oded Schwartz , Technical University Berlin
Expanders and Communication-Avoiding Algorithms		 video
Tuesday, January 19, 2010 Katalin Vesztergombi , Eotvos Lorand University, Budapest, Hungary
Limits of Randomly Grown Graph Sequences
Tuesday, December 22, 2009 The talks will resume during the School of Mathematics Second Term.
Monday, December 21, 2009 The talks will resume during the School of Mathematics Second Term.
Tuesday, December 15, 2009 Moritz Hardt , Princeton University
An Algorithmic Proof of Forster's Lower Bound		 video
Monday, December 14, 2009 Iftach Ilan Haitner , Microsoft Research New England
A Parallel Repetition Theorem for Any Interactive Argument		 video
Tuesday, December 8, 2009 Russell Impagliazzo , University of California at San Diego; Member, School of Mathematics
Algorithmic Dense Model Theorems, Decompositions, and Regularity Theorems		 video
Monday, December 7, 2009 Joshua Brody , Dartmouth College
The NOF Communication Complexity of Multiparty Pointer Jumping		 video
Tuesday, December 1, 2009 Russell Impagliazzo , University of California at San Diego; Member, School of Mathematics
Algorithmic Dense Model Theorems, Decompositions, and Regularity Theorems
Monday, November 30, 2009 There will be no talk today due to trave times from the Thanksgiving Holiday.
Tuesday, November 24, 2009 Madhur Tulsiani , Member, School of Mathematics
Arithmetic Progressions in Primes		 video
Monday, November 23, 2009 Moni Naor , The Weizmann Institute of Science
Privacy of Dynamic Data: Continual Observation and Pan Privacy		 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 Alexandra Kolla , Member, School of Mathematics
Graph and Subgraph Sparsification and its Implications to Linear System Solving and Transforming Graphs into Expanders		 video
Monday, November 9, 2009 Adi Livnat , University of California, Berkeley
Why Sex?
Tuesday, November 3, 2009 Martin Kassabov , Cornell University; von Neumann Fellow, School of Mathematics
Constructions of Expanders Using Group Theory		 video
Monday, November 2, 2009 Troy Lee , Rutgers, The State University of New Jersey
Grothendieck Inequalities, XOR Games, and Communication Complexity		 video
Tuesday, October 27, 2009 No Seminar Due to FOCS 2009 Symposium
<a href="http://www.cc.gatech.edu/focs2009/">http://www.cc.gatech.edu/focs2009/</a>
Monday, October 26, 2009 No Seminar Due to FOCS 2009 Symposium
<a href="http://www.cc.gatech.edu/focs2009/">http://www.cc.gatech.edu/focs2009/</a>
Tuesday, October 20, 2009 Dana Moshkovitz , Member, School of Mathematics
Hardness of Projection Games		 video
Monday, October 19, 2009 Or Meir , The Weizmann Institute of Science
PCPs of Sub-Constant Error Via Derandomized Direct Product		 video
Tuesday, October 13, 2009 William Matthews , University of California at San Diego
Using Local Conductance to Give Improved Algorithms for Unique Games		 video
Monday, October 12, 2009 Ramamohan Paturi , University of California at San Diego
On The Complexity of Circuit Satisfiability		 video
Tuesday, October 6, 2009 Amir Yehudayoff , Member, School of Mathematics
The Completeness of the Permanent		 video
Monday, October 5, 2009 Itai Arad , Hebrew University of Jerusalem
The Detectability Lemma and Quantum Gap Amplification		 video
Tuesday, September 29, 2009 Ben Reichardt , University of Waterloo, Canada
Span Programs and Quantum Query Algorithms		 video
Monday, September 28, 2009 No Seminar Today in Observance of Yom Kippur
Tuesday, September 22, 2009 Amir Yehudayoff , Member, School of Mathematics
The Completeness of the Permanent		 video
Monday, September 21, 2009 Nikhil Srivastava , Yale University
Twice-Ramanujan Sparsifiers		 video
Tuesday, September 15, 2009 Swastik Kopparty , Massachusetts Institute of Technology
Affine Dispersers from Subspace Polynomials		 video
Monday, September 14, 2009 Shubhangi Saraf , Massachusetts Institute of Technology
Blackbox Polynomial Identity Testing for Depth 3 Circuits

Sponsored by:

National Science Foundation

State of New Jersey 		Abacus

Abacus 		Analytical engine by Charles Babbage

"Analytical Engine"

by Charles Babbage 		Turing Machine

Turing Machine