| Monday, June 13, 2005 | The PCP Theorem by Gap Amplification Irit Dinur (Hebrew University of Jerusalem) |
| Wednesday, June 1, 2005 | Computing Equilibria Christos Papadimitriou (University of California, Berkeley) |
| Tuesday, May 31, 2005 | Approximation Algorithms for Unique Games Luca Trevisan (University of California, Berkeley) |
| Tuesday, May 31, 2005 | A Formal Model for Dynamic Programming Russell Impagliazzo (University of California, San Diego) |
| Monday, May 9, 2005 | On Routing Without Regret Avrim Blum (Carnegie Mellon University) |
| Friday, May 6, 2005 | An O(log n log log n) Space Algorithm for Undirected st-Connectivity Vladimir Trifonov (University of Texas at Austin) |
| Tuesday, May 3, 2005 | Extremal Erodos-Szekeres Permutations and Square Young Tableaux Dan Romik (MSRI, Berkeley) |
| Monday, May 2, 2005 | Capacities of Graph Powers Eyal Lubetzky (Tel Aviv University) |
| Tuesday, April 26, 2005 | Lower Bounds for the Noisy Broadcast Problem Navin Goyal (Rutgers University) |
| Monday, April 25, 2005 | On Non-uniform Multicommodity Buy-at-Bulk Network Design Adriana Karagiozova (Princeton University) |
| Tuesday, April 19, 2005 | Additive Approximation for Edge-Deletion Problems Noga Alon (IAS) |
| Monday, April 18, 2005 | Towards Strong Inapproximability Results in the Lovasz-Schrijver Hierarchy Iannis Tourlakis (Princeton University) |
| Wednesday, April 13, 2005 | Linear-Degree Extractors and the NP-Completeness of Approximating Clique and Chromatic Number David Zuckerman (University of Texas) |
| Tuesday, April 12, 2005 | Cuts, Quadratic Programs and in Between Muli Safra (IAS) |
| Monday, April 11, 2005 | Aggregating Inconsistent Information: Ranking and Custering Nir Ailon (Princeton University) |
| Tuesday, April 5, 2005 | Even Hole Free Graphs Maria Chudnovsky (IAS) |
| Monday, April 4, 2005 | Conflict-Free Colorings Shakhar Smorodinsky (Courant Institute) |
| Tuesday, March 29, 2005 | Controlled Linear Programming and Linear Complementarity for Some Infinite Games in NP $\cap$ coNP Sergei Vorobyov (Uppsala University, Sweden) |
| Monday, March 28, 2005 | Max Cut - A Combinatorial Perspective Benny Sudakov (Princeton University) |
| Tuesday, March 22, 2005 | Information Theory and Probability Estimation Alon Orlitsky (University of California at San Diego) |
| Tuesday, March 22, 2005 | 1 Dimensional Diffusion Limited Aggregation (DLA) Gideon Amir (Weizmann Institute) |
| Monday, March 21, 2005 | Network Games and the Price of Stability or Anarchy Eva Tardos (Cornell University) |
| Tuesday, March 15, 2005 | Gems of Combinatorial Number Theory Avi Wigderson (IAS) |
| Monday, March 14, 2005 | Random Walk on Oriented Hypercubes Tibor Szabo (ETH, Zurich) |
| Tuesday, March 8, 2005 | Excited Random Walk Gady Kozma (IAS) |
| Monday, March 7, 2005 | Graph Homomorphisms, Statistical Physics, and Limits of Graph Sequences Laszlo Lovasz (Microsoft Research, Redmond, WA and Eotvos Lorand University, Budapest) |
| Tuesday, March 1, 2005 | Pseudorandom Walks in Biregular Graphs and the RL vs. L. Problem Omer Reingold (Weizmann Institute) |
| Monday, February 28, 2005 | Undirected Graph Connectivity in Log-Space (SL=L) Omer Reingold (Weizmann Institute) |
| Tuesday, February 22, 2005 | Quadratic Forms on Graphs Konstantin Makarychev (Princeton University) |
| Monday, February 21, 2005 | Cryptography in NC0 Yuval Ishai (Technion) |
| Tuesday, February 15, 2005 | Fixed Point Properties of Random Groups Lior Silberman (Princeton University) |
| Monday, February 14, 2005 | The Dynamics of Boosting Cynthia Rudin (New York University) |
| Tuesday, February 8, 2005 | Forcing with Random Variables Jan Krajicek (Academy of Sciences of Czech Republic) |
| Monday, February 7, 2005 | Embedding Almost Spanning Bounded Degree Trees Michael Krivelevich (Tel Aviv University) |
| Tuesday, February 1, 2005 | Geometric symmetrizations in high dimension Bo'az Klartag (IAS) |
| Monday, January 31, 2005 | Approximation algorithms and Grothendieck type inequalities Noga Alon (IAS) |
| Monday, January 31, 2005 | Extremal graphs, recursive functions and a separation theorem in property testing Asaf Shapira (Tel Aviv University) |
| Tuesday, January 25, 2005 | The Tic-Tac-Toe Theory Jozsef Beck (Rutgers University) |
| Monday, January 24, 2005 | Shorter and Simpler PCPs Madhu Sudan (MIT) |
| Tuesday, January 18, 2005 | On Lattices, Learning with Errors, Random Linear Codes, and Cryptography Oded Regev (Tel-Aviv University) |
| Monday, January 17, 2005 | Multicommodity flow, well-linked terminals, and routing problems Chandra Chekuri (Bell Labs) |
| Tuesday, December 14, 2004 | Variance/Entropy Decomposition Techniques for Proving Fast Mixing of the Glauber Dynamics Dror Weitz (IAS) |
| Monday, December 13, 2004 | On Learning Random Decision Trees and DNF Formulas Rocco Servedio (Columbia University) |
| Tuesday, December 7, 2004 | Variance/Entropy Decomposition Techniques for Proving Fast Mixing of the Glauber Dynamics Dror Weitz (IAS) |
| Monday, December 6, 2004 | Several Geometric Applications of Chernoff Estimates: A Zigzag Approximation for Balls and Some Random Matrices Shiri Artstein (Princeton University and IAS) |
| Tuesday, November 30, 2004 | On Random Bernoulli Matrices: Singularity and Determinant Van Vu (University of California at San Diego) |
| Monday, November 29, 2004 | An Unconditional Study of Computational Zero Knowledge Salil Vadhan (Harvard University) |
| Tuesday, November 23, 2004 | Learnability and Automatizability Michael Alekhnovich (IAS) |
| Monday, November 22, 2004 | Using Nondeterminism to Amplify Hardness Emanuele Viola (Harvard University) |
| Tuesday, November 16, 2004 | Slow Mixing of Local Dynamics for Colourings and Independent Sets David Galvin (IAS) |
| Monday, November 15, 2004 | On Sensitivity and Chaos Elchanan Mossel (University of California, Berkeley) |
| Tuesday, November 9, 2004 | Slow Mixing of Local Dynamics for Colourings and Independent Sets David Galvin (IAS) |
| Monday, November 8, 2004 | Approximation Algorithms for Embeddings into Low-Dimensional Spaces Piotr Indyk (MIT) |
| Tuesday, November 2, 2004 | Explicit Constructions of Bipartite Ramsey Graphs
Boaz Barak and Guy Kindler (IAS) |
| Monday, November 1, 2004 | Influences and Decision Tree Complexity Michael Saks (Rutgers University) |
| Tuesday, October 26, 2004 | Explicit Constructions of Bipartite Ramsey Graphs Boaz Barak and Guy Kindler (IAS) |
| Monday, October 25, 2004 | Tic-Tac-Toe Games: Exact Values of Infinitely Many Game Numbers Jozsef Beck (Rutgers University) |
| Tuesday, October 19, 2004 | NO SEMINAR DUE TO FOCS CONFERENCE
|
| Monday, October 18, 2004 | NO SEMINAR DUE TO FOCS CONFERENCE
|
| Tuesday, October 12, 2004 | The Intersection of a Matroid and a Simplicial Complex Eli Berger (IAS) |
| Monday, October 11, 2004 | Toward Privacy in Public Databases Cynthia Dwork (Microsoft Research) |
| Tuesday, October 5, 2004 | The Complexity of Agreement Scott Aaronson (IAS) |
| Monday, October 4, 2004 | Lower Bounds for Linear Degeneracy Testing Nir Ailon (Princeton University) |
| Monday, September 27, 2004 | On the Measure of Interesting Families via Spectral Methods Ehud Friedgut (Hebrew University) |
Sponsored by: National Science Foundation State of New Jersey
|
 Abacus |
 "Analytical Engine" by Charles Babbage |
 Turing Machine |