2009-2010 Seminars

Tuesday, May 25, 2010 Avi Wigderson , Professor, School of Mathemtics
The Stepanov Method
Monday, May 24, 2010 Boaz Barak , Princeton University
Subsampling Mathematical Relaxations and Average-case Complexity
Tuesday, May 18, 2010 Madhur Tulsiani , Member, School of Mathematics
Reductions Between Expansion Problems
Tuesday, May 11, 2010 Amir Yehudayoff , Member, School of Mathematics
Small-Bias Sets
Tuesday, May 4, 2010 Sergei Konyagin , Moscow State University; Member, School of Mathemtics
Explicit Construction of RIP Matrices, Matrices With Small Coherence, and Related Problems
Tuesday, April 27, 2010 Dana Moshkovitz , Member, School of Mathemtics
Hardness of Approximately Solving Linear Equations Over Reals
Tuesday, April 20, 2010 Zeev Dvir , Member, School of Mathemtics
Matching Vector Codes
Monday, April 19, 2010 Vijay Vazirani , Georgia Institute of Technology
Can Complexity Theory Ratify the Invisible Hand of the Market?
Tuesday, April 13, 2010 Eyal Lubetzky , Microsoft Research Redmond
Critical Slowdown for the Ising Model on the Two-Dimensional Lattice
Monday, April 12, 2010 James Lee , University of Washington
Cover Times, Blanket Times, and Majorizing Measures
Tuesday, April 6, 2010 Peter Sarnak , Professor, School of Mathematics
Mobius Randomness and Dynamics
Monday, April 5, 2010 Mark Braverman , Microsoft Research New England
Compressing Bounded-Round Communication
Tuesday, March 30, 2010 Valentine Kabanets , Simon Fraser University; Member, School of Mathematics
A Combinatorial Proof of the Chernoff-Hoeffding Bound, With Applications to Direct-Product Theorems
Monday, March 29, 2010 There will be no TCS/DM Seminar talk today
Tuesday, March 23, 2010 No talk today in lieu of the U.S. Income Tax Seminar for Members
Monday, March 22, 2010 Rajat Mittal , Rutgers, The State Unviersity of New Jersey
Product Rules in Semidefinite Programming
Tuesday, March 16, 2010 Amir Yehudayoff , Member, School of Mathematics
Pseudorandom Generators for Regular Branching Programs
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
Tuesday, March 2, 2010 Boaz Barak , Princeton University
Computational Complexity and Information Asymmetry in Financial Products
Monday, March 1, 2010 Manoj M. Prabhakaran , University of Illinois at Urbana-Champaign
A Theory of Cryptographic Complexity
Tuesday, February 23, 2010 Hamed Hatami , Princeton University; Member, School of Mathematics
Testing Correlations and Inverse Theorems
Monday, February 22, 2010 Rocco Servedio , Columbia University
Average Sensitivity of Polynomial Threshold Functions
Tuesday, February 16, 2010 Prasad Raghavendra , University of Washington
Complexity of Constraint Satisfaction problems: Exact and Approximate
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
Monday, February 8, 2010 Julia Wolf , Rutgers, The State University of New Jersey
Interpreting Polynomial Structure Analytically
Tuesday, February 2, 2010 Avi Wigderson , Professor, School of Mathematics
Representation Theory and Expansion in Groups
Monday, February 1, 2010 Hoi H. Nguyen , Rutgers, The State University
A New Approach to the Inverse Littlewood-Offord Problem
Tuesday, January 26, 2010 Avi Wigderson , Professor, School of Mathematics
Representation Theory and Expansion in Groups
Monday, January 25, 2010 Oded Schwartz , Technical University Berlin
Expanders and Communication-Avoiding Algorithms
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
Monday, December 14, 2009 Iftach Ilan Haitner , Microsoft Research New England
A Parallel Repetition Theorem for Any Interactive Argument
Tuesday, December 8, 2009 Russell Impagliazzo , University of California at San Diego; Member, School of Mathematics
Algorithmic Dense Model Theorems, Decompositions, and Regularity Theorems
Monday, December 7, 2009 Joshua Brody , Dartmouth College
The NOF Communication Complexity of Multiparty Pointer Jumping
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
Monday, November 23, 2009 Moni Naor , The Weizmann Institute of Science
Privacy of Dynamic Data: Continual Observation and Pan Privacy
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
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
Monday, November 2, 2009 Troy Lee , Rutgers, The State University of New Jersey
Grothendieck Inequalities, XOR Games, and Communication Complexity
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
Monday, October 19, 2009 Or Meir , The Weizmann Institute of Science
PCPs of Sub-Constant Error Via Derandomized Direct Product
Tuesday, October 13, 2009 William Matthews , University of California at San Diego
Using Local Conductance to Give Improved Algorithms for Unique Games
Monday, October 12, 2009 Ramamohan Paturi , University of California at San Diego
On The Complexity of Circuit Satisfiability
Tuesday, October 6, 2009 Amir Yehudayoff , Member, School of Mathematics
The Completeness of the Permanent
Monday, October 5, 2009 Itai Arad , Hebrew University of Jerusalem
The Detectability Lemma and Quantum Gap Amplification
Tuesday, September 29, 2009 Ben Reichardt , University of Waterloo, Canada
Span Programs and Quantum Query Algorithms
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
Monday, September 21, 2009 Nikhil Srivastava , Yale University
Twice-Ramanujan Sparsifiers
Tuesday, September 15, 2009 Swastik Kopparty , Massachusetts Institute of Technology
Affine Dispersers from Subspace Polynomials
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