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