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, �cole 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 Erd�s 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