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