CSDM Seminars
Tuesday, May 3, 2011  CSDM Seminars II will be resume first term of the 201112 academic year


Monday, May 2, 2011  CSDM Seminars I will resume first term of the 201112 academic year


Tuesday, April 26, 2011  Madhur Tulsiani , Member, School of Mathematics
Quadratic GoldreichLevin Theorems 

Monday, April 25, 2011  Rocco Servidio , Columbia University
Learning and Testing kModel Distributions 

Friday, April 22, 2011  Alex Kontorovich , Stony Brook University
On Zaremba's Conjecture 

Friday, April 22, 2011  Zeev Dvir , Princeton University; Member, School of Mathematics
Monotone Expanders  Constructions and Applications 

Friday, April 22, 2011  Larry Guth , University of Toronto; Member, School of Mathematics
The Polynomial Method and Applications From Finite Field Kakeya to Distinct Distances 

Tuesday, April 19, 2011  Rong Ge , Princeton University
New Tools for Graph Coloring 

Monday, April 18, 2011  Dmitry Gavinsky , NEC Research Laboratories
Quantum Fingerprints that Keep Secrets 

Monday, April 11, 2011  Nick Harvey , University of Waterloo
Graph Sparsification by EdgeConnectivity and Random Spanning Trees 

Tuesday, April 5, 2011  Nikhil Srivastava , Member, School of Mathematics
ZeroOne Rounding of Singular Vectors 

Monday, April 4, 2011  Ashwin Nayak , University of Waterloo
Improved Bounds for the Randomized Decision Tree Complexity of Recursive Majority 

Tuesday, March 29, 2011  Grant Schoenbeck , Princeton University
General Hardness Amplification of Predicates and Puzzles 

Monday, March 28, 2011  Xi Chen , Columbia University
Nonnegatively Weighted #CSPs: An Effective Complexity Dichotomy 

Tuesday, March 22, 2011  
Monday, March 21, 2011  Ryan O'Donnell , Carnegie Mellon University; Member, School of Mathematics
Pareto Optimal Solutions for Smooth Analysts 

Tuesday, March 15, 2011  Daniel Kane , Harvard University
A PRG for Gaussian Polynomial Threshold Functions 

Monday, March 14, 2011  Amir Shpilka , Technion; on leave at Microsoft Research New England
On the Fourier Spectrum of Symmetric Boolean Functions 

Tuesday, March 8, 2011  Russell Impagliazzo , University of California, San Diego; Member, School of Mathematics
Relativized Separations of WorstCase and AverageCase Complexities for NP 

Monday, March 7, 2011  Mohit Singh , McGill University
A Randomized Rounding Approach for Symmetric TSP 

Tuesday, March 1, 2011  Eric Blais , Carnegie Mellon University
Property Testing Lower Bounds Via Communication Complexity 

Monday, February 28, 2011  Charanjit Jutla , IBM T. J. Watson Research Center
A Completeness Theorem for PseudoLinear Functions with Applications to UC Security 

Tuesday, February 22, 2011  Shubhangi Saraf , Massachusetts Institute of Technology
Local Testing and Decoding of Sparse Linear Codes 

Monday, February 21, 2011  Amit Chakrabarti , Dartmouth College
Information Cost Tradeoffs for AUGMENTED INDEX and Streaming Language Recognition 

Tuesday, February 15, 2011  Toniann Pitassi , University of Toronto
Automatizability and Simple Stochastic Games 

Monday, February 14, 2011  Shachar Lovett , Member, School of Mathematics
An Elementary Proof of AntiConcentration of Polynomials in Gaussian Variables 

Tuesday, February 8, 2011  Rishi Saket , Princeton University
Bypassing UGC From Some Optimal Geometric Inapproximability Results 

Monday, February 7, 2011  Edo Liberty , Yahoo! Research, Haifa, Isreal
Fast Random Projections 

Tuesday, February 1, 2011  Swastik Kopparty , Member, School of Mathematics
On The Complexity of Computing Roots and Residuosity Over Finite Fields 

Monday, January 31, 2011  Jelani Nelson , Massachusetts Institute of Technology
Sparsifying and Derandomizing the JohnsonLindenstrauss Transform 

Tuesday, January 25, 2011  R\'emi Monasson , Ecole Normale Superieure; Simons Center for Systems Biology, IAS
Learning with Boolean Threshold Functions, a Statistical Physics Perspective 

Monday, January 24, 2011  Hoeteck Wee , Queens College, City University of New York
Universal OneWay Hash Functions via Inaccessible Entropy 

Tuesday, January 18, 2011  Ankur Moitra , Massachusetts Institute of Technology
Efficiently Learning Mixtures of Gaussians 

Monday, January 17, 2011  Sergei Vassilvitskii , Yahoo! Research
CrossValidation and MeanSquare Stability 

Tuesday, December 14, 2010  Larry Guth , University of Toronto; Member, School of Mathematics
Erdos Distinct distance Problem in the Plane 

Monday, December 13, 2010  Paul Seymour , Princeton University
Colouring Tournaments 

Tuesday, December 7, 2010  Andrew Appel , Princeton University
Introduction to the Coq Proof Assistant 

Monday, December 6, 2010  Assaf Naor , Courant Institute of Mathematical Sciences
Nonlinear Dvoretzky Theory 

Tuesday, November 30, 2010  Paul Beame , University of Washington; Member, School of Mathematics
Hardness Escalation and the Rank of Polynomial Threshold Proofs 

Monday, November 29, 2010  Dana Moshkovitz , Massachusetts Institute of Technology
SelfCorrection, Distance Estimation and Local Testing of Codes 

Monday, November 29, 2010  Scott Aaronson , Massachusetts Institute of Technology
The Permanents of Gaussian Matrices 

Tuesday, November 23, 2010  Richard Ehrenborg , University of Kentucky; Member, School of Mathematics
Counting Pattern Avoiding Permutations Via Integral Operators 

Monday, November 22, 2010  David Conlon , University of Cambridge
Combinatorial Theorems in Random Sets 

Tuesday, November 16, 2010  Menachem Kojman , Ben Gurion University of the Negev; Member, School of Mathematics
Planar Convexity, Infinite Perfect Graphs and Lipschitz Continuity 

Monday, November 15, 2010  Andrzej Rucinski , Adam Mickiewicz University in Polznan, Poland; Emory University
Fractional Perfect Matchings in Hypergraphs 

Tuesday, November 9, 2010  Nikhil Srivastava , Member, School of Mathematics
An Elementary Proof of the Restricted Invertibility Theorem 

Monday, November 8, 2010  Jacob Fox , Massachusetts Institute of Technology
The Graph Removal Lemma 

Tuesday, November 2, 2010  Rani Hod , Tel Aviv University
3/2 Firefighters Are Not Enough 

Tuesday, November 2, 2010  Shachar Lovett , Member, School of Mathematics
Fourier Spectrum of Polynomials Over Finite Fields 

Monday, November 1, 2010  Elad Haramaty , Technion
On the Structure of Cubic and Quartic Polynomials 

Tuesday, October 26, 2010  (No CSDM talk today  FOCS 2010 Symposium


Monday, October 25, 2010  (No CSDM talk today  FOCS 2010 Symposium


Tuesday, October 19, 2010  Zeev Dvir , Member, School of Mathematics
Rank Bounds for Design Matrices with Applications to Combinatorial Geometry and Locally Correctable Codes 

Monday, October 18, 2010  Arnab Bhattacharyya , Massachusetts Institute of Technology
A Unified Framework for Testing LinearInvariant Properties 

Tuesday, October 12, 2010  Michael Saks , Rutgers, The State University of New Jersey
Approximating the Longest Increasing Subsequence in Polylogarithmic Time 
video 
Monday, October 11, 2010  Srikanth Srinivasan , Member, School of Mathematics
The Complexity of the Noncommutative Determinant 
video 
Tuesday, October 5, 2010  Shachar Lovett , Member, School of Mathematics
Pseudorandom Generators for CCO[p] and the Fourier Spectrum of LowDegree Polynomials Over Finite Fields 
video 
Monday, October 4, 2010  Jozsef Beck , Rutgers, The State University of New Jersey
Superuniformity of the typical billiard path (proof included) 
video 
Tuesday, September 28, 2010  Swastik Kopparty , Member, School of Mathematics
HighRate Codes with Sublinear Time Decoding 
video 
Monday, September 27, 2010  Van Vu , Rutgers, The State University of New Jersey
The Condition Number of a Random Matrix: From von NeumannGoldstine to SpielmanTeng 
video 
Tuesday, September 21, 2010  Ryan O'Donnell , Carnegie Mellon University; Member, School of Mathematics
Invariance Principles in Theoretical Computer Science 
video 
Monday, September 20, 2010  Benny Sudakov , University of California at Los Angeles
Dependent Random Choice and Approximate Sidorenko's Conjecture 
video 