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 | Randomness Extractors
Avi Wigderson (School of Mathematics, Institute for Advanced Study) video |
| Wednesday, December 3, 2008 | Substitution Sequences at Primes
Peter Sarnak (School of Mathematics, Institute for Advanced Study/Department of Mathematics, Princeton University) video |
| Wednesday, December 3, 2008 | When Do Sparse Sets Have Dense Models?
Russell Impagliazzo (University of California at San Diego and Member, School of Mathematics) video |
| Wednesday, December 3, 2008 | Exponential Sums, Equidistribution and Pseudo-Randomness
Jean Bourgain (School of Mathematics, Institute for Advanced Study) 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) |
Sponsored by: National Science Foundation State of New Jersey
|
 Abacus |
 "Analytical Engine" by Charles Babbage |
 Turing Machine |