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