Seminars

Tuesday, May 14, 2013	No Seminar Talk
Monday, May 13, 2013	Raghu Meka , DIMACS (Rutgers); Member, School of Mathematics Association Schemes, Non-Commutative Polynomials and Lasserre Lower Bounds for Planted Clique
Monday, May 13, 2013	Andrew Drucker , Member, School of Mathematics Nondeterministic Direct Product Reductions and the Success Probability of SAT Solvers
Tuesday, May 7, 2013	No Seminar Talk
Monday, May 6, 2013	Rotem Oshman , University of Toronto Tight Bounds for Set Disjointness in the Message-Passing Model
Tuesday, April 30, 2013	Michal Feldman , Hebrew University of Jerusalem Combinatorial Walrasian Equilibrium
Monday, April 29, 2013	Michael Rabin , Harvard University and Columbia University Cryptography and Preventing Collusion in Second Price (Vickery) Auctions
Tuesday, April 23, 2013	Klim Efremenko , Tel-Aviv University; Member, School of Mathematics Uncertainty Principle
Monday, April 22, 2013	Daniel Kane , Stanford University Diffuse Decompositions of Polynomials
Tuesday, April 16, 2013	No Seminar Talk
Monday, April 15, 2013	Irit Dinur , Weizmann Institute; Radcliffe institute Analytical Approach to Parallel Repetition
Tuesday, April 9, 2013	Jozsef Beck , Rutgers, The State University of New Jersey "What is Geometric Entropy, and Does it Really Increase?"
Monday, April 8, 2013	No Seminar Talk
Tuesday, April 2, 2013	Sushant Sachdeva , Princeton University An Arithmetic Analogue of Fox's Improved Triangle Removal Lemma
Monday, April 1, 2013	Thomas Vidick , Massachusetts Institute of Technology Device Independence: A New Paradigm for Randomness Manipulation?
Tuesday, March 26, 2013	No Seminar Talk
Monday, March 25, 2013	Madhu Sudan , Microsoft Research New Locally Decodable Codes from Lifting
Tuesday, March 19, 2013	Hao Huang , University of California, Los Angeles; Member, School of Mathematics Sensitivity Versus Block Sensitivity, II
Monday, March 18, 2013	Eli Ben-Sasson , Technion; Massachusetts Institute of Technology Constant Rate PCPs for Circuit-SAT with Sublinear Query Complexity
Tuesday, March 12, 2013	Hao Huang , University of California, Los Angeles; Member, School of Mathematics Sensitivity Versus Block Sensitivity, I
Monday, March 11, 2013	Tim Roughgarden , Stanford University Intractability in Algorithmic Game Theory
Tuesday, March 5, 2013	Avi Wigderson , School of Mathematics, IAS Derandomization of Probabilistic Logspace (The Nisan Variations)
Monday, March 4, 2013	Dhruv Mubayi , University of Illinois at Chicago Quasirandom Hypergraphs
Tuesday, February 26, 2013	Avi Wigderson , School of Mathematics, IAS Derandomizing BPL?
Monday, February 25, 2013	Emmanuel Abbe , Princeton University Polar Codes and Randomness Extraction for Structured Sources
Tuesday, February 19, 2013	Shubhangi Saraf , Rutgers, The State University of New Jersey The Chasm at Depth 3
Monday, February 18, 2013	Penny Haxell , University of Waterloo Connectedness, Sperner's Lemma and Combinatorial Problems
Tuesday, February 12, 2013	Alex Lubotzky , Hebrew University High Dimensional Expanders and Ramanujan Complexes
Monday, February 11, 2013	Liu Yang , School of Computer Science, Carnegie Mellon University Mathematical Theories of Interaction with Oracles: Active Property Testing and New Models for Learning Boolean Functions
Tuesday, February 5, 2013	Manor Mendel , The Open University of Israel; Member, School of Mathematics Ramsey Theory for Metric Spaces
Monday, February 4, 2013	Gil Kalai , Hebrew University; Yale University Influences, Traces, Tribes, and Perhaps Also Thresholds
Tuesday, January 29, 2013	Manor Mendel , The Open University of Israel; Member, School of Mathematics The Ribe Program
Monday, January 28, 2013	Xin Li , University of Washington New Independent Source Extractors with Exponential Improvement
Tuesday, January 22, 2013	Jelani Nelson , Member, School of Mathematics Sparsity Lower Bounds for Dimensionality Reducing Maps
Monday, January 21, 2013	Sebastien Bubeck , Princeton University Clique Number of Random Geometric Graphs in High Dimension
Tuesday, January 15, 2013	Jelani Nelson , Member, School of Mathematics OSNAP: Faster Numerical Linear Algebra Algorithms Via Sparser Subspace Embeddings
Monday, January 14, 2013	Pavel Hrubes , University of Washington On Bilinear Complexity
Tuesday, December 18, 2012	(1) Raghu Meka and (2) Avi Wigderson , (1) DIMACS; (2) IAS The SOS (aka Lassere/Positivestellensatz/Sum-of-Squares) System
Monday, December 17, 2012	No Seminar
Tuesday, December 11, 2012	Or Meir , Stanford University; Member, School of Mathematics Combinatorial PCPs with Short Proofs
Monday, December 10, 2012	Vijay Vazirani , Georgia Institute of Technology Matching: A New Proof for an Ancient Algorithm
Tuesday, December 4, 2012	Ran Raz , Weizmann Institute; Member, School of Mathematics Delegation for Bounded Space
Monday, December 3, 2012	Mark Braverman , Princeton University Information Complexity and Exact Communication Bounds
Tuesday, November 27, 2012	Jing Chen , Massachusetts Institute of Technology; Member, School of Mathematics Computational Complexity in Mechanism Design
Monday, November 26, 2012	Michael Forbes , Massachusetts Institute of Technology Polynomial Identity Testing of Read-Once Oblivious Algebraic Branching Progress
Tuesday, November 20, 2012	Joseph Landsberg , Texas A&M University On the Complexity of Matrix Multiplication and Other Tensors
Monday, November 19, 2012	Jin-Yi Cai , University of Wisconsin A Complete Dichotomy Rises from the Capture of Vanishing Signatures
Tuesday, November 13, 2012	No Seminar (Oberwolfach)
Monday, November 12, 2012	No Seminar (Oberwolfach)
Tuesday, November 6, 2012	Jing Chen , Massachusetts Institute of Technology; Member, School of Mathematics Games, Solution Concepts, and Mechanism Design: A Very Short Introduction
Monday, November 5, 2012	Ben Rossman , Tokyo Institute of Technology Query Complexity of Black-Box Search
Monday, October 29, 2012	Michal Feldman , Hebrew University and Harvard University Combinatorial Walrasian Equilibrium
Tuesday, October 23, 2012	No Seminar (FOCS Meeting)
Monday, October 22, 2012	No Seminar (FOCS Meeting)
Tuesday, October 16, 2012	Andrew Drucker , Massachusetts Institute of Technology; Member, School of Mathematics On the AND- and OR-Conjectures: Limits to Efficient Preprocessing
Monday, October 15, 2012	Tsuyoshi Ito , NEC Laboratories America, Inc. A Multi-Prover Interactive proof for NEXP Sound Against Entangled Provers
Tuesday, October 9, 2012	Hao Huang , University of California, Los Angeles; Member, School of Mathematics On the Conjectures of Nonnegative $k$-Sum and Hypergraph Matching
Monday, October 8, 2012	Amir Shpilka , Technion Identity Testing of Tensors, Low Rank Recovery and Compressed Sensing
Tuesday, October 2, 2012	Alex Russell , University of Connecticut Plug your ears! Graph isomorphism, siren of the algebraic seas, calls to your quantum helmsman.
Monday, October 1, 2012	Cris Moore , Santa Fe Institute Random Vectors, Random Matrices, Permuted Products, Permanents, and Diagrammatic Fun
Tuesday, September 25, 2012	Greg Kuperberg , University of California, Davis Koiran + Geometric Topology implies "Knottedness is in NP"
Monday, September 24, 2012	Greg Kuperberg , University of California, Davis The Computational Complexity of Geometric Topology Problems
Tuesday, May 22, 2012	No seminar today (STOC Conference)
Monday, May 21, 2012	No seminar today (STOC Conference)
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 Log-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