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