2003-2004 seminars
| Monday, September 22, 2003 | Yehuda Lindell, IBM Watson Impossibility Results for the Composition of Secure Two-Party Protocols |
| Tuesday, September 23, 2003 | Boaz Barak, IAS Lower Bounds for Non-Blacks-Box Zero-Knowledge |
| Monday, September 29, 2003 | Michael Kearns, University of Pennsylvania Network Models for Game Theory and Economics |
| Tuesday, September 30, 2003 | Farid Ablayev, Kazan State University On the Computational Power of Classical and Quantum Branching Programs |
| Tuesday, October 7, 2003 | Russell Impagliazzo, IAS Memorization and DPLL: Formula Caching Proof Systems |
| Monday, October 20, 2003 | Grigori Mints, Stanford University Propositional Logic of Continuous Transformations |
| Tuesday, October 21, 2003 | Eyal Rozenman, Hebrew University A New Explicit Construction of Constant-Degree Expander Cayley Graphs |
| Wednesday, October 22, 2003 | Ahuva Mu'alem, Hebrew University Towards a Characterization of Truthful Combinatorial Auctions |
| Monday, October 27, 2003 | Nicholas Pippenger, Princeton University Probability Theory and Covering Problems |
| Tuesday, October 28, 2003 | Eyal Rozenman, Hebrew University A New Explicit Construction of Constant-Degree Expander Cayley Graphs (Cont'd) |
| Monday, November 3, 2003 | Scott Aaronson, University of California Berkeley Multilinear Formulas and Skepticism of Quantum Computing |
| Tuesday, November 4, 2003 | Russel Impagliazzo, IAS Priority Algorithms: Greedy Graph Algorithms |
| Monday, November 10, 2003 | Erik Demaine, Massachusetts Institute of Technology Folding and Unfolding in Computational Geometry |
| Tuesday, November 11, 2003 | Dorit Aharonov, Hebrew University Approximating the Shortest and Closest Vector in a Lattice to within Sqrt(n) Lie in NP Intersect coNP |
| Monday, November 17, 2003 | Claire Kenyon, Ecole Polytechnique and Institut Universitaire de France Approximation Algorithms for Packing |
| Tuesday, November 18, 2003 | Mikhail Alekhnovitch, IAS Exponential Lower Bounds for the Running Time of DPLL Algorithms on Satisfiable Formulas |
| Monday, November 24, 2003 | Adam Kalai, TTI, Chicago Boosting in the Presence of Noise |
| Monday, December 1, 2003 | Sanjeev Arora, Princeton University Expander Flows and a sqrt{log n} - Approximation for Graph Expansion/Sparsest cut |
| Tuesday, December 2, 2003 | Avi Wigderson, IAS and Hebrew University Derandomized "low degree" tests via "epsilon-biased" sets, with Applications to Short Locally Testable Codes and PCPs |
| Monday, December 8, 2003 | Valentine Kabanets, Simon Fraser University Complexity of Succinct Zero-sum Games |
| Tuesday, December 9, 2003 | Ryan O'Donnell, IAS Learning Mixtures of Product Distributions |
| Monday, January 19, 2004 | Tom Hayes, Toyota Technological Institute, Chicago Randomly Sampling Graph Colorings |
| Tuesday, January 20, 2004 | Ran Raz, Weizmann Institute Multi-Linear Formulas for Permanent and Determinant are of Super-Polynomial Size |
| Tuesday, January 20, 2004 | Josh Buresh-Oppenheim, University of Toronto Rank Bounds and Integrality Gaps for Cutting Planes Procedures |
| Monday, January 26, 2004 | Mario Szegedy, Rutgers University Spectra of Quantized Walks and a $\sqrt{\delta\epsilon}$-Rule |
| Tuesday, January 27, 2004 | James R. Lee, Berkeley University Metric Decomposition: Coping with Boundaries |
| Monday, February 2, 2004 | Aner Shalev, Hebrew University Probabilistic Generation of Finite Simple Groups, Random Walks, Fuchsian Groups and Witten's zeta Function |
| Tuesday, February 3, 2004 | Noga Alon, Tel Aviv University CutNorm, Grothendieck's Inequality, and Approximation Algorithms for Dense Graphs |
| Monday, February 9, 2004 | Nathan Segerlind, IAS Using Hypergraph Homomorphisms to Guess Three Secrets |
| Tuesday, February 10, 2004 | Peter Winkler, Bell Labs and IAS Some Vexing Combinatorial and Mixing Problems |
| Monday, February 16, 2004 | Christos Papadimitriou, University of California Berkeley Nash Equilibria and Complexity |
| Tuesday, February 17, 2004 | Maria Chudnovsky, Princeton, CMI and IAS The Structure of Clawfree Graphs |
| Wednesday, February 18, 2004 | Roy Meshulam, Technion, Haifa Laplacians, Homology and Hypergraph Matching |
| Monday, February 23, 2004 | Ravi Kumar, IBM Almaden Research Center On Separating Nondeterminism and Randomization in Communication Complexity |
| Monday, February 23, 2004 | Mark Braverman, University of Toronto On the Computability of Julia Sets |
| Tuesday, February 24, 2004 | Stephen Cook, University of Toronto Making Sense of Bounded Arithmetic |
| Monday, March 1, 2004 | Yonatan Bilu, Hebrew University Quasi-Ramanujan 2-lifts - A New Construction of Expander Graphs |
| Tuesday, March 2, 2004 | Toniann Pitassi, IAS On a Model for Backtracking |
| Monday, March 8, 2004 | Avraham Neyman, Institute of Mathematics, Hebrew University Online Concealed Correlation by Boundedly Rational Players |
| Tuesday, March 9, 2004 | Boaz Barak, IAS Extracting Randomness from Few Independent Sources |
| Monday, March 15, 2004 | Amir Shpilka, The Weizmann Institute Locally Testable Cyclic Codes |
| Tuesday, March 16, 2004 | Subhash Khot, IAS BCH Codes, Augmented Tensor Products and Hardness of the Shortest Vector Problem in Lattices |
| Monday, March 22, 2004 | Moni Naor, Weizmann Institute of Science Spam and Pebbling |
| Tuesday, March 23, 2004 | Manindra Agrawal, IAS Efficient Primality Testing |
| Monday, March 29, 2004 | Mike Capalbo, DIMACS Graph Products are (almost!) Practical |
| Tuesday, March 30, 2004 | Andris Ambainis, IAS Search by Quantum Walks |
| Monday, April 5, 2004 | Van Vu, University of California, San Diego A Near Optimal Bound on Erdos Distinct Distances in high Dimensions |
| Tuesday, April 6, 2004 | Jan Krajicek, IAS Strong Proof Systems and Hard Tautologies |
| Monday, April 12, 2004 | Benny Sudakov, Princeton University Solving Extremal Problems Using Stability Approach |
| Tuesday, April 13, 2004 | Alexander Razborov, IAS Guessing More Secrets via List Decoding |
| Monday, April 19, 2004 | Andrew Yao, Princeton University Some Optimality Results in Bounded-Storage Cryptography |
| Tuesday, April 20, 2004 | Andris Ambainis, IAS Search by Quantum Walks II |
| Monday, April 26, 2004 | Jon Kleinberg, Cornell University Network Failure Detection and Graph Connectivity |
| Tuesday, April 27, 2004 | Ryan O'Donnell, IAS Optimal Inapproximability Results for MAX-CUT and Other 2-Variable CSPs |
| Monday, May 3, 2004 | Sean Hallgren, NEC Research, Princeton Fast Quantum Algorithms for Computing the Unit Group and Class Group of a Number Field |
| Tuesday, May 4, 2004 | Subhash Khot, IAS Ruling Out PTAS for Graph Min-Bisection |
| Monday, May 10, 2004 | Manoj Prabhakaran, Princeton University New Notions of Security: Universal Composability without Trusted Setup |
| Tuesday, May 11, 2004 | Yuval Peres, University of California, Berkeley Two Topics on the Interface of Probability and Algorithms |
| Monday, May 17, 2004 | Yuval Rabani, Technion, on Sabbatical at Cornell University Some Results on $k$-gonal Metrics |
| Tuesday, May 18, 2004 | Subhash Khot, IAS Ruling Out PTAS for Graph Min-Bisection (continued) |
| Monday, May 24, 2004 | Dana Moshkovitz Algorithmic Construction of Sets for k-Restrictions |
| Tuesday, May 25, 2004 | Peter Winkler, Bell Labs and IAS Tournaments, Boxes and Non-Transitive Dice |