CSDM Seminars
| Tuesday, May 15, 2012 | Klim Efremenko , Tel Aviv University
From Irreducible Representations to Locally Decodable Codes |
|
| Monday, May 14, 2012 | Nisheeth Vishnoi , Microsoft Research, Bangalore
Are Lattice Based Cryptosystems Secure Enough? |
|
| Tuesday, May 8, 2012 | Raghu Meka , Member, School of Mathematics
Pseudorandomness from Shrinkage |
|
| Monday, May 7, 2012 | Pooya Hatami , University of Chicago
Topology of Norms Defined by Systems of Linear forms |
|
| Tuesday, May 1, 2012 | Abhishek Bhowmick , University of Texas at Austin
Lower Bounds for Matching Vector Codes |
|
| Monday, April 30, 2012 | Mario Szegedy , Rutgers, The State University of New Jersey
Randomized Greedy Algorithms for the Maximum Matching Problem with New Analysis |
|
| Tuesday, April 24, 2012 | Srikanth Srinivasan , DIMACS
Pseudorandom Generators for Read-Once ACC^0 |
|
| Monday, April 23, 2012 | Salil Vadhan , Harvard University; Visiting Researcher Microsoft Research SVC; Visiting Scholar Stanford University
Computational Entropy |
|
| Tuesday, April 17, 2012 | Laszlo Lovasz , Eotvos Lorand University, Budapest; Member, School of Mathematics
Nondeterministic Property Testing |
|
| Monday, April 16, 2012 | Sushant Sachdeva , Princeton University
Near-Linear Time Approximation Algorithm for Balanced Separator |
|
| Tuesday, April 10, 2012 | Swastik Kopparty , Rutgers University
List-Decoding Multiplicity Codes |
|
| Monday, April 9, 2012 | Endre Csoka , Eotvos Lorand University, Budapest, Hungary
Random Local Algorithms |
|
| Tuesday, April 3, 2012 | Parikshit Gopalan , Microsoft Research Silicon Valley, Mountain View, CA
Better Pseudorandom Generators from Milder Pseudorandom Restrictions |
|
| Monday, April 2, 2012 | Pablo Azar , Massachusetts Institute of Technology
Rational Proofs |
|
| Tuesday, March 27, 2012 | Luca Trevisan , Stanford University
Higher-Order Cheeger Inequalities |
|
| Monday, March 26, 2012 | Jan Vondrak , IBM Almaden
Hardness of Randomized Truthful Mechanisms for Combinatorial Auctions |
|
| Tuesday, March 20, 2012 | Miklos Abert , Alfred Renyi Institute of Mathematics, Budapest
Graph Convergence, Parameter Testing and Group Actions |
|
| Tuesday, March 20, 2012 | Shachar Lovett , Member, School of Mathematics
The Quasi-Polynomial Freiman-Ruzsa Theorem of Sanders |
|
| Monday, March 19, 2012 | Gregory Valiant , University of California, Berkeley
Optimal Estimators for Entropy, Support Size, and Related Properties |
|
| Tuesday, March 13, 2012 | Jelani Nelson , Member, School of Mathematics
Applications of FT-Mollification II |
|
| Monday, March 12, 2012 | Mina Teicher , Bar-Ilan University; Member, School of Mathematics
Computational Aspects in the Braid Group and Applications to Cryptography |
|
| Tuesday, March 6, 2012 | Jelani Nelson , Member, School of Mathematics
Applications of FT-Mollification |
|
| Monday, March 5, 2012 | Emanuele Viola , Northeastern University
The Complexity of Distributions |
|
| Tuesday, February 28, 2012 | Christos Papadimitriou , University of California at Berkeley
Complexity, Approximability, and Mechanism Design |
|
| Monday, February 27, 2012 | Noga Zewi , Technion
An Additive Combinatorics Approach to the Long-Rank Conjecture in Communication Complexity |
|
| Thursday, February 23, 2012 | Amir Yehudayoff , Technion--Israel Institute of Technology
Building Expanders in Three Steps |
|
| Thursday, February 23, 2012 | Boaz Barak , Microsoft Research New England
Zero Knowledge Proofs and Nuclear Disarmament |
|
| Tuesday, February 21, 2012 | Joel Spencer , Courant Institute, NYU
Finding Needles in Exponential Haystacks |
|
| Monday, February 20, 2012 | Venkat Guruswami , Carnegie Mellon University
Lasserre Hierarchy, Higher Eigenvalues, and Graph Partitioning |
|
| Tuesday, February 14, 2012 | Benjamin Matschke , Member, School of Mathematics
On the Colored Tverberg Problem |
|
| Monday, February 13, 2012 | Andrew Drucker , Massachusetts Institute of Technology
High-Confidence Predictions under Adversarial Uncertainty |
|
| Tuesday, February 7, 2012 | David Zuckerman , University of Texas at Austin; Member, School of Mathematics
Randomness Extraction: A Survey |
|
| Monday, February 6, 2012 | Fan Chung , University of California at San Diego
Graphlets: A Spectral Perspective for Graph Limits |
|
| Tuesday, January 31, 2012 | Avi Wigderson , Herbert H. Maass Professor, School of Mathematics
A Survey of Lower Bounds for the Resolution Proof System |
|
| Monday, January 30, 2012 | Santosh Vempala , Georgia Institute of Technology
Nearly Optimal Deterministic Algorithms Via M-Ellipsoids |
|
| Tuesday, January 24, 2012 | Russell Impagliazzo , University of California, San Diego; Member, School of Mathematics
A Tutorial on the Likely Worst-Case Complexities of NP-Complete Problems |
|
| Monday, January 23, 2012 | Michael Saks , Rutgers, The State University of New Jersey
An Optimal Lower Bound for File Maintenance |
|
| Tuesday, December 13, 2011 | Christopher Beck , Princeton University
Time-Space Tradeoffs in Resolution: Superpolynomial Lower Bounds for Superlinear Space |
|
| Monday, December 12, 2011 | Pavel Hrubes , University of Calgary
Monotone Unification Problems |
|
| Tuesday, December 6, 2011 | Menachem Magidor , Hebrew University
Can the Continuum Problem be Solved? |
|
| Monday, December 5, 2011 | Mark Braverman , Princeton University
Towards Coding for Maximum Errors in Interactive Communication |
|
| Tuesday, November 29, 2011 | Raghu Meka , Member, School of Mathematics
Shorter Long Code and Applications to Unique Games |
|
| Monday, November 28, 2011 | Oded Regev , CNRS-ENS-Paris and Tel Aviv University
Entropy-Based Bounds on Dimension Reduction in L_1 |
|
| Tuesday, November 22, 2011 | Raghu Meka , Member, School of Mathematics
Shorter Long Code and Applications to Unique Games |
|
| Monday, November 21, 2011 | Siavosh Benabbas , University of Toronto
An Isoperimetric Inequality for the Hamming Cube and Integrality Gaps in Bounded-Degree Graphs |
|
| Tuesday, November 15, 2011 | Ankur Moitra , Massachusetts Institute of Technology; Member, School of Mathemtics
Vertex Sparsification: An Introduction, Connections and Applications |
|
| Monday, November 14, 2011 | Mihalis Yannakakis , Columbia University
Polynomial Time Algorithms for Multi-Type Branching Processes and Stochastic Context-Free Grammars |
|
| Tuesday, November 8, 2011 | Ankur Moitra , Massachusetts Institute of Technology; Member, School of Mathematics
Vertex Sparsification: An Introduction, Connections and Applications |
|
| Monday, November 7, 2011 | Sigal Oren , Cornell University
How Bad is Forming Your Own Opinion |
|
| Tuesday, November 1, 2011 | No Seminar (CCI Quantum Computation Workshop)
|
|
| Monday, October 31, 2011 | Jeff Kahn , Rutgers, The State University of New Jersey
Mantel's Theorem for Random Graphs |
|
| Tuesday, October 25, 2011 | No Seminar (FOCS 2011 Meeting)
|
|
| Monday, October 24, 2011 | No Seminar (FOCS 2011 Meeting)
|
|
| Tuesday, October 18, 2011 | Ohad Feldheim , Tel Aviv University
Rigidity of 3-Colorings of the d-Dimensional Discrete Torus |
|
| Monday, October 17, 2011 | Michael Krivelevich , Tel Aviv University
On the Number of Hamilton Cycles in Psdueo-Random Graphs |
|
| Tuesday, October 11, 2011 | Balazs Szegedy , University of Toronto; Member, School of Mathematics
Limit Theories and Higher Order Fourier Analysis |
|
| Monday, October 10, 2011 | Arkadev Chattopadhyay , University of Toronto
A Little Advice Can Be Very Helpful |
|
| Tuesday, October 4, 2011 | Balazs Szegedy , University of Toronto; Member, School of Mathematics
Limit Theories and Higher Order Fourier Analysis |
|
| Monday, October 3, 2011 | Jing Chen , Massachusetts Institute of Technology
Mechanism Design With Set-Theoretic Beliefs |
|
| Tuesday, September 27, 2011 | Shubhangi Saraf , Microsoft Research; Member, School of Mathematics
Tight Lower Bounds for 2-query LCCs Over Finite fields |
|
| Monday, September 26, 2011 | Benny Sudakov , University of California, Los Angeles
Nonnegative k-Sums, Fractional Covers, and Probability of Small Deviations |
|
| Tuesday, September 20, 2011 | Shachar Lovett , Member, School of Mathematics
Existence of Small Families of t-wise Independent Permutations and t-Designs Via Local Limit Theorems |
|
| 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 |
|
| Friday, April 22, 2011 | Swastik Kopparty , Member, School of Mathematics
The Correlation of Multiplicative Characters with Polynomials over Finite Fields |
|
| Friday, April 22, 2011 | Peter Varju , Princeton University
Random Walks in Linear Groups |
|
| 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 |
Sponsored by: National Science Foundation State of New Jersey
|
 Abacus |
 "Analytical Engine" by Charles Babbage |
 Turing Machine |