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