# 2008-2009 Seminars

 Friday, August 21, 2009 Adventures of the Mind Tuesday, June 23, 2009 Matrix Products and Subgraph Problems Virginia Vassilevska (Member, School of Mathematics) Tuesday, June 16, 2009 Extensions to the Method of Multiplicities with Applications to Kakeya Sets and Mergers Zeev Dvir (Member, School of Mathematics) Tuesday, June 9, 2009 Linear Systems Over Composite Moduli Arkadev Chattopadhyay (Member, School of Mathematics) Monday, June 8, 2009 Quasi-One-Way Functions Andrej Bogdanov (Chinese University of Hong Kong) Tuesday, June 2, 2009 COMPUTER SCIENCE/DISCRETE MATH II No Seminar Due to STOC Conference Monday, June 1, 2009 COMPUTER SCIENCE/DISCRETE MATH I No Seminar Due to STOC Conference Tuesday, May 26, 2009 On the Complexity of Boolean Functions in Different Characteristics Amir Shpilka (Technion) Tuesday, May 26, 2009 Constraints, Logic and Derandomization Gabor Kun (Simon Fraser University and Member, School of Mathematics) Monday, May 25, 2009 COMPUTER SCIENCE/DISCRETE MATH I Institute Closed in Observance of Memorial Day Tuesday, May 19, 2009 To Check is To Know is To Prove Doron Zeilberger (Rutgers, The State University) Monday, May 18, 2009 The Density Hales-Jewett Theorem and Open-Source Mathematics Ryan O'Donnell (Carnegie Mellon University) Tuesday, May 12, 2009 The Circle Method Craig Spencer (Member, School of Mathematics) Monday, May 11, 2009 SDP Integrality Gaps with Local L1-Embeddability Subhash Khot (Courant Institute, NYU) Tuesday, May 5, 2009 List Decoding Product and Interleaved Codes Venkatesan Guruswami (University of Washington/Carnegie Mellon University) Monday, May 4, 2009 Lower Bounds for Randomized Communication Complexity Mike Saks (Rutgers, The State University) Tuesday, April 28, 2009 Values and Patterns Alon Orlitsky (Depts. of ECE and CSE, University of California at San Diego) Monday, April 27, 2009 Values and Patterns Alon Orlitsky (Depts. of ECE and CSE, University of California at San Diego) Tuesday, April 21, 2009 Beyond Planarity Jacob Fox (Princeton University) Monday, April 20, 2009 The Constant-Depth Complexity of k-Clique Ben Rossman (Massachusetts Institute of Technology) Tuesday, April 14, 2009 The TCS/DM Seminar scheduled for today has been cancelled. Monday, April 13, 2009 Bounded Independence Fools Halfspaces Emanuele Viola (Northeastern University) Tuesday, April 7, 2009 On the Parallel Repetition Theorem Thomas Holenstein (Princeton University) Monday, April 6, 2009 Public Key Cryptography from Different Assumptions Benny Applebaum (Princeton University) Tuesday, March 31, 2009 COMPUTER SCIENCE/DISCRETE MATH II No Seminar Due to DIMACS "Property Testing" Workshop Monday, March 30, 2009 COMPUTER SCIENCE/DISCRETE MATH I No Seminar Due to DIMACS "Property Testing" Workshop Tuesday, March 24, 2009 Direct Sums in Randomized Communication Complexity Anup Rao (Member, School of Mathematics) Monday, March 23, 2009 Symmetry and Approximability of Submodular Maximization Problems Jan Vondrak (Princeton University) Tuesday, March 17, 2009 No CSDM Seminar Today Due to US Income Tax Seminar for Members Monday, March 16, 2009 Simple Algorithms for Sequential k-Independent Graphs Allan Borodin (University of Toronto, Canada) Tuesday, March 10, 2009 Affine Extractors Over Prime Fields Amir Yehudayoff (Member, School of Mathematics, Institute for Advanced Study) Monday, March 9, 2009 NP and MA Do Not Contain coNP in Multiparty Communication Complexity Dmitry Gavinsky (NEC Laboratories America, Inc.) Tuesday, March 3, 2009 Graph Homomorphisms With Complex Values: A Dichotomy Theorem Xi Chen (Member, School of Mathematics) Monday, March 2, 2009 Finding Sparse Cuts Locally Using Evolving Sets Yuval Peres (Microsoft Research, Redmond) Tuesday, February 24, 2009 Algorithmic Versions of Dense Model Theorems Russell Impagliazzo (University of California at San Diego and Member, School of Mathematics) Monday, February 23, 2009 The Convergence of Bird Flocking Bernard Chazelle (Princeton University) Tuesday, February 17, 2009 Algorithmic Versions of Dense Model Theorems Russell Impagliazzo (University of California at San Diego and Member, School of Mathematics) Monday, February 16, 2009 Approximating Submodular Functions Everywhere Nick Harvey (Microsoft Research, MIT) Wednesday, February 11, 2009 On P vs NP, Geometric Complexity Theory, and the Riemann Hypothesis Ketan Mulmuley (University of Chicago) video Tuesday, February 10, 2009 On P vs NP, Geometric Complexity Theory, and the Riemann Hypothesis Ketan Mulmuley (University of Chicago) video Monday, February 9, 2009 On P vs NP, Geometric Complexity Theory, and the Riemann Hypothesis Ketan Mulmuley (Unviersity of Chicago) video Tuesday, February 3, 2009 Poly-logarithmic Independence Fools ACO Circuits Mark Braverman (Microsoft Research New England) Monday, February 2, 2009 Towards a Calculus for Non-Linear Spectral Gaps Assaf Naor (Courant Institute, NYU) Tuesday, January 27, 2009 The XOR Lemma -- A Quarter Century of Proofs Avi Wigderson (School of Mathematics, Institute for Advanced Study) Monday, January 26, 2009 The Limits of Advice Scott Aaronson (Massachusetts Institute of Technology) Tuesday, January 20, 2009 Resilient and Equilibrium-Less Mechanism Design Silvio Micali and Paul Valiant (Massachusetts Institute of Technology) Monday, January 19, 2009 Noise-Resilient Group Testing: Limitations and Constructions Mahdi Cheraghchi (EPFL, Lausanne, Switzerland) Tuesday, January 13, 2009 COMPUTER SCIENCE/DISCRETE MATH II No CSDM Seminar Today Monday, January 12, 2009 COMPUTER SCIENCE/DISCRETE MATH I No CSDM Seminar Today Tuesday, December 16, 2008 Extractors for Varieties Zeev Dvir (Member, School of Mathematics) Monday, December 15, 2008 Direct-Product Testing, and a New 2-Query PCPs Valentine Kabanets (Simon Fraser University) Tuesday, December 9, 2008 Extractors for Varieties Zeev Dvir (Member, School of Mathematics) Monday, December 8, 2008 Cutoff Phenomena for Random Walks on Random Regular Graphs Eyal Lubetzky (Microsoft Research) Monday, December 8, 2008 Convergent Sequences of Sparse Graphs Bela Bollobas (University of Cambridge/University of Memphis) Wednesday, December 3, 2008 Substitution Sequences at Primes Peter Sarnak (School of Mathematics, Institute for Advanced Study/Department of Mathematics, Princeton University) video Tuesday, December 2, 2008 Combinatorial Reasoning in Information Theory Noga Alon (Tel Aviv University and Member, School of Mathematics) Monday, December 1, 2008 Derandomizing Algorithms on Product Distributions Avinatan Hassidim (Massachusetts Institute of Technology) Tuesday, November 25, 2008 Complexity of Equational Proof Systems Pavel Hrubes (Member, School of Mathematics) Monday, November 24, 2008 Quantum Algorithms Using the Curvelet Transform Yi-Kai Liu (Caltech) Monday, November 24, 2008 Large Induced Trees in $K_r$-Free Graphs Jacob Fox (Princeton University) Tuesday, November 18, 2008 Complexity of Equational Proof Systems Pavel Hrubes (Member, School of Mathematics) Monday, November 17, 2008 Scalably Scheduling Processes with Arbitrary Speedup Curves Jeff Edmonds (York University, Toronto, Ont., Canada) Tuesday, November 11, 2008 Dichotomy Conjecture for Constraint Satisfaction Problems Gabor Kun (Renyi Institute and Member, School of Mathematics) Monday, November 10, 2008 Almost-Natural Proofs Timothy Chow (IDA, Princeton) Tuesday, November 4, 2008 Dichotomy Conjecture for Constraint Satisfaction Problems Gabor Kun (Renyi Institute and Member, School of Mathematics) Monday, November 3, 2008 Rounded Parallel Repetitions of Unique Games David Steurer (Princeton University) Tuesday, October 28, 2008 http://focs2008.org No Seminar Due to FOCS 2008 Symposium Monday, October 27, 2008 http://focs2008.org No Seminar Due to FOCS 2008 Symposium Tuesday, October 21, 2008 Group Representation Patterns in Digital Processing Shamgar Gurevich and Ronny Hadani (University of California at Berkeley and University of Chicago) Monday, October 20, 2008 k-Wise Independent Random Graphs Asaf Nussboim (The Weizmann Institute) Monday, October 20, 2008 Affine Dispersers from Subspace Polynomials Eli Ben-Sasson (Technion) Tuesday, October 14, 2008 Lower Bounds for Circuits with MOD_m Gates Arkadev Chattopadhyay (Member, School of Mathematics) Monday, October 13, 2008 Average Case to Worst Case Reductions for Polynomials Shachar Lovett (Hebrew University of Jerusalem) Tuesday, October 7, 2008 Lower Bounds for Circuits with MOD_m Gates Arkadev Chattopadhyay (Member, School of Mathematics) video Monday, October 6, 2008 Color Coding, Balanced Hashing and Approximate Counting Noga Alon (Member, School of Mathematics) Monday, October 6, 2008 List-Decoding Reed-Muller Codes Over Small Fields David Zuckerman (University of Texas at Austin) Tuesday, September 30, 2008 A Survey of Time Lower Bounds by Algorithmic Arguments Richard Ryan Williams (Member, School of Mathematics) Monday, September 29, 2008 Composition of Rational Functions Michael Zieve (Member, School of Mathematics) Tuesday, September 23, 2008 Multilinear Computation Amir Yehudayoff (Member, School of Mathematics) Monday, September 22, 2008 Hypergraph Ramsey Numbers Benny Sudakov (University of California at Los Angeles) Tuesday, September 16, 2008 Multilinear Computation Amir Yehudayoff (Member, School of Mathematics) Monday, September 15, 2008 On a Conjecture of Linial and Berge Eli Berger (University of Haifa) Tuesday, September 9, 2008 A Simple Proof of Bazzi's Theorem Alexander Razborov (University of Chicago)