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 |
 "Analytical Engine" by Charles Babbage |
 Turing Machine |
