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 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)