2011-2012 Seminars

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