20082009 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  QuasiOneWay 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 HalesJewett Theorem and OpenSource 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 L1Embeddability 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 ConstantDepth Complexity of kClique 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 kIndependent 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  Polylogarithmic Independence Fools ACO Circuits Mark Braverman (Microsoft Research New England) 
Monday, February 2, 2009  Towards a Calculus for NonLinear 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 EquilibriumLess Mechanism Design Silvio Micali and Paul Valiant (Massachusetts Institute of Technology) 
Monday, January 19, 2009  NoiseResilient 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  DirectProduct Testing, and a New 2Query 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 YiKai 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  AlmostNatural 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  <a href="http://focs2008.org">http://focs2008.org</a>
No Seminar Due to FOCS 2008 Symposium 
Monday, October 27, 2008  <a href="http://focs2008.org">http://focs2008.org</a>
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  kWise Independent Random Graphs Asaf Nussboim (The Weizmann Institute) 
Monday, October 20, 2008  Affine Dispersers from Subspace Polynomials Eli BenSasson (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  ListDecoding ReedMuller 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) 