20042005 seminars
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 stConnectivity Vladimir Trifonov (University of Texas at Austin) 
Tuesday, May 3, 2005  Extremal ErodosSzekeres 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 Nonuniform Multicommodity BuyatBulk Network Design Adriana Karagiozova (Princeton University) 
Tuesday, April 19, 2005  Additive Approximation for EdgeDeletion Problems Noga Alon (IAS) 
Monday, April 18, 2005  Towards Strong Inapproximability Results in the LovaszSchrijver Hierarchy Iannis Tourlakis (Princeton University) 
Wednesday, April 13, 2005  LinearDegree Extractors and the NPCompleteness 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  ConflictFree 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 LogSpace (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 TicTacToe 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 (TelAviv University) 
Monday, January 17, 2005  Multicommodity flow, welllinked 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 LowDimensional 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  TicTacToe 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) 