# 2004-2005 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 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)