CSDM Seminars

Tuesday, May 3, 2011 CSDM Seminars II will be resume first term of the 2011-12 academic year
Monday, May 2, 2011 CSDM Seminars I will resume first term of the 2011-12 academic year
Tuesday, April 26, 2011 Madhur Tulsiani , Member, School of Mathematics
Quadratic Goldreich-Levin Theorems
Monday, April 25, 2011 Rocco Servidio , Columbia University
Learning and Testing k-Model 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 Edge-Connectivity and Random Spanning Trees
Tuesday, April 5, 2011 Nikhil Srivastava , Member, School of Mathematics
Zero-One 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
Non-negatively 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 Worst-Case and Average-Case 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 Pseudo-Linear 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 Anti-Concentration 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 Johnson-Lindenstrauss 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 One-Way 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
Cross-Validation and Mean-Square 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
Self-Correction, 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 Linear-Invariant 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 Non-commutative Determinant
video
Tuesday, October 5, 2010 Shachar Lovett , Member, School of Mathematics
Pseudorandom Generators for CCO[p] and the Fourier Spectrum of Low-Degree Polynomials Over Finite Fields
video
Monday, October 4, 2010 Jozsef Beck , Rutgers, The State University of New Jersey
Super-uniformity of the typical billiard path (proof included)
video
Tuesday, September 28, 2010 Swastik Kopparty , Member, School of Mathematics
High-Rate 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 Neumann-Goldstine to Spielman-Teng
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