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) |