# 2003-2004 seminars

 Monday, September 22, 2003 Yehuda Lindell, IBM WatsonImpossibility Results for the Composition of Secure Two-Party Protocols Tuesday, September 23, 2003 Boaz Barak, IASLower Bounds for Non-Blacks-Box Zero-Knowledge Monday, September 29, 2003 Michael Kearns, University of PennsylvaniaNetwork Models for Game Theory and Economics Tuesday, September 30, 2003 Farid Ablayev, Kazan State UniversityOn the Computational Power of Classical and Quantum Branching Programs Tuesday, October 7, 2003 Russell Impagliazzo, IASMemorization and DPLL: Formula Caching Proof Systems Monday, October 20, 2003 Grigori Mints, Stanford UniversityPropositional Logic of Continuous Transformations Tuesday, October 21, 2003 Eyal Rozenman, Hebrew UniversityA 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 UniversityProbability Theory and Covering Problems Tuesday, October 28, 2003 Eyal Rozenman, Hebrew UniversityA New Explicit Construction of Constant-Degree Expander Cayley Graphs (Cont'd) Monday, November 3, 2003 Scott Aaronson, University of California BerkeleyMultilinear Formulas and Skepticism of Quantum Computing Tuesday, November 4, 2003 Russel Impagliazzo, IASPriority Algorithms: Greedy Graph Algorithms Monday, November 10, 2003 Erik Demaine, Massachusetts Institute of TechnologyFolding and Unfolding in Computational Geometry Tuesday, November 11, 2003 Dorit Aharonov, Hebrew UniversityApproximating 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 FranceApproximation Algorithms for Packing Tuesday, November 18, 2003 Mikhail Alekhnovitch, IASExponential Lower Bounds for the Running Time of DPLL Algorithms on Satisfiable Formulas Monday, November 24, 2003 Adam Kalai, TTI, ChicagoBoosting in the Presence of Noise Monday, December 1, 2003 Sanjeev Arora, Princeton UniversityExpander Flows and a sqrt{log n} - Approximation for Graph Expansion/Sparsest cut Tuesday, December 2, 2003 Avi Wigderson, IAS and Hebrew UniversityDerandomized "low degree" tests via "epsilon-biased" sets, with Applications to Short  Locally Testable Codes and PCPs Monday, December 8, 2003 Valentine Kabanets, Simon Fraser UniversityComplexity of Succinct Zero-sum Games Tuesday, December 9, 2003 Ryan O'Donnell, IASLearning Mixtures of Product Distributions Monday, January 19, 2004 Tom Hayes, Toyota Technological Institute, ChicagoRandomly Sampling Graph Colorings Tuesday, January 20, 2004 Ran Raz, Weizmann InstituteMulti-Linear Formulas for Permanent and Determinant are of Super-Polynomial Size Tuesday, January 20, 2004 Josh Buresh-Oppenheim, University of TorontoRank Bounds and Integrality Gaps for Cutting Planes Procedures Monday, January 26, 2004 Mario Szegedy, Rutgers UniversitySpectra of Quantized Walks and a $\sqrt{\delta\epsilon}$-Rule Tuesday, January 27, 2004 James R. Lee, Berkeley UniversityMetric Decomposition:  Coping with Boundaries Monday, February 2, 2004 Aner Shalev, Hebrew UniversityProbabilistic Generation of Finite Simple Groups, Random Walks, Fuchsian Groups and Witten's zeta Function Tuesday, February  3, 2004 Noga Alon, Tel Aviv UniversityCutNorm, Grothendieck's Inequality, and Approximation Algorithms for Dense Graphs Monday, February 9, 2004 Nathan Segerlind, IASUsing Hypergraph Homomorphisms to Guess Three Secrets Tuesday, February 10, 2004 Peter Winkler, Bell Labs and IASSome Vexing Combinatorial and Mixing Problems Monday, February 16, 2004 Christos Papadimitriou, University of California BerkeleyNash Equilibria and Complexity Tuesday, February 17, 2004 Maria Chudnovsky, Princeton, CMI and IASThe Structure of Clawfree Graphs Wednesday, February 18, 2004 Roy Meshulam, Technion, HaifaLaplacians, Homology and Hypergraph Matching Monday, February 23, 2004 Ravi Kumar, IBM Almaden Research CenterOn Separating Nondeterminism and Randomization in Communication Complexity Monday, February 23, 2004 Mark Braverman, University of TorontoOn the Computability of Julia Sets Tuesday, February 24, 2004 Stephen Cook, University of TorontoMaking Sense of Bounded Arithmetic Monday, March 1, 2004 Yonatan Bilu, Hebrew UniversityQuasi-Ramanujan 2-lifts - A New Construction of Expander Graphs Tuesday, March 2, 2004 Toniann Pitassi, IASOn a Model for Backtracking Monday, March 8, 2004 Avraham Neyman, Institute of Mathematics, Hebrew UniversityOnline Concealed Correlation by Boundedly Rational Players Tuesday, March 9, 2004 Boaz Barak, IASExtracting Randomness from Few Independent Sources Monday, March 15, 2004 Amir Shpilka, The Weizmann InstituteLocally Testable Cyclic Codes Tuesday, March 16, 2004 Subhash Khot, IASBCH Codes, Augmented Tensor Products and Hardness of the Shortest Vector Problem in Lattices Monday, March 22, 2004 Moni Naor, Weizmann Institute of ScienceSpam and Pebbling Tuesday, March 23, 2004 Manindra Agrawal, IASEfficient Primality Testing Monday, March 29, 2004 Mike Capalbo, DIMACSGraph Products are (almost!) Practical Tuesday, March 30, 2004 Andris Ambainis, IASSearch by Quantum Walks Monday, April 5, 2004 Van Vu, University of California, San DiegoA Near Optimal Bound on Erd�s Distinct Distances in high Dimensions Tuesday, April 6, 2004 Jan Krajicek, IASStrong Proof Systems and Hard Tautologies Monday, April 12, 2004 Benny Sudakov, Princeton UniversitySolving Extremal Problems Using Stability Approach Tuesday, April 13, 2004 Alexander Razborov, IASGuessing More Secrets via List Decoding Monday, April 19, 2004 Andrew Yao, Princeton UniversitySome Optimality Results in Bounded-Storage Cryptography Tuesday, April 20, 2004 Andris Ambainis, IASSearch by Quantum Walks II Monday, April 26, 2004 Jon Kleinberg, Cornell UniversityNetwork Failure Detection and Graph Connectivity Tuesday, April 27, 2004 Ryan O'Donnell, IASOptimal Inapproximability Results for MAX-CUT and Other 2-Variable CSPs Monday, May 3, 2004 Sean Hallgren, NEC Research, PrincetonFast Quantum Algorithms for Computing the Unit Group and Class Group of a Number Field Tuesday, May 4, 2004 Subhash Khot, IASRuling Out PTAS for Graph Min-Bisection Monday, May 10, 2004 Manoj Prabhakaran, Princeton UniversityNew Notions of Security:  Universal Composability without Trusted Setup Tuesday, May 11, 2004 Yuval Peres, University of California, BerkeleyTwo Topics on the Interface of Probability and Algorithms Monday, May 17, 2004 Yuval Rabani, Technion, on Sabbatical at Cornell UniversitySome Results on $k$-gonal Metrics Tuesday, May 18, 2004 Subhash Khot, IASRuling Out PTAS for Graph Min-Bisection (continued) Monday, May 24, 2004 Dana MoshkovitzAlgorithmic Construction of Sets for k-Restrictions Tuesday, May 25, 2004 Peter Winkler, Bell Labs and IASTournaments, Boxes and Non-Transitive Dice