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) |
Sponsored by: National Science Foundation State of New Jersey
|
 Abacus |
 "Analytical Engine" by Charles Babbage |
 Turing Machine |