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 |
Sponsored by: National Science Foundation State of New Jersey
|
 Abacus |
 "Analytical Engine" by Charles Babbage |
 Turing Machine |