2012-2013 Seminars

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