Preliminary Program for FOCS 2003 Saturday October 11th 2003 Tutorials Day at Radcliffe Institute for Advanced Study TUTORIAL 1: 9:30am - 11:30 pm, Chair: Paul Beame Avrim Blum: Lunch (on your own) TUTORIAL 2: 1:20pm - 3:20 pm, Chair: Michael Mitzenmacher Dana Randall: TUTORIAL 3: 3:50pm-5:50pm, Chair: Avi Wigderson Eli Upfal: Welcome Reception 7:00 pm - 8:30pm ------------------------------------------------------------------------ Sunday October 12th 2003 Morning SESSION 1: 8:45 am - 10:25 am, Chair: Chandra Chekuri * Perfect Graph Recognition, Gerard Cornuejols and Xinming Liu and Kristina Vuskovic * On Certain Connectivity Properties of the Internet Topology, Milena Mihail and Christos Papadimitriou and Amin Saberi * Paths, Trees and minimum latency tours, Kamalika Chaudhuri and Brighten Godfrey and Satish Rao and Kunal Talwar * Approximation Algorithms for Orienteering and Discounted-Reward TSP, Avrim Blum and Shuchi Chawla and David Karger and Terran Lane and Adam Meyerson and Maria Minkoff * A 2/3 Approximation for Maximum Asymmetric TSP by Decomposing Directed Regular Multigraphs, Haim Kaplan and Moshe Lewenstein and Nira Shafrir and Maxim Sviridenko SESSION 2: 10:50am - 12:10pm, Chair: Eyal Kushilevitz * On the Implementation of Huge Random Objects, Oded Goldreich and Shafi Goldwasser and Asaf Nussboim * Zero-Knowledge Sets, Silvio Micali and Michael Rabin and Joe Kilian * Deterministic Extractors for Bit-Fixing Sources and Exposure-Resilient Cryptography, Jesse Kamp and David Zuckerman * On the (In)security of the Fiat-Shamir Paradigm, Shafi Goldwasser and Yael Tauman Lunch (Provided) Afternoon SESSION 3: 1:40pm - 3:00pm, Chair: Valentine Kabanets * Locally Testable Cyclic Codes, Laszlo Babai and Amir Shpilka and Daniel Stefankovic * List Decoding Using the XOR Lemma, Luca Trevisan * On $\epsilon$-Biased Generators in NC^0, Elchanan Mossel and Amir Shpilka and Luca Trevisan * A Unifying Approach for Proving Hardcore Predicates Using List Decoding, Adi Akavia and Shafi Goldwasser and Muli Safra SESSION 4: 3:25pm - 4:45pm, Chair: Michael Mitzenmacher * Instability of FIFO at Arbitrarily Low Rates in the Adversarial Queueing Model, Rajat Bhattacharjee and Ashish Goel * Proofs of the Parisi and Coppersmith-Sorkin Conjectures for the Finite Random Assignment Problem, Chandra Nair and Balaji Prabhakar and Mayank Sharma * Better Turing: asymptotically optimal probability estimation, Alon Orlitsky and Narayana P. Santhanam and Junan Zhang * Learning DNF from Random Walks, Nader Bshouty and Elchanan Mossel and Ryan O'Donnell and Rocco Servedio SESSION 5: 5:10pm - 6:30pm, Chair: John Watrous * Quantum Search of Spatial Regions, Scott Aaronson and Andris Ambainis * A Lattice Problem in Quantum NP, Dorit Aharonov and Oded Regev * A lower bound for bounded round quantum communication complexity of set disjointness, Rahul Jain and Jaikumar Radhakrishnan and Pranab Sen * Polynomial degree vs. quantum query complexity, Andris Ambainis Business Meeting 9:00 pm - 10:00 pm ------------------------------------------------------------------------ Monday October 13th 2003 Morning SESSION 6: 8:45 am - 10:25 am, Chair: Erik Demaine * An In-Place Sorting with O(n log n) Comparisons and O(n) Moves, Gianni Franceschini and Viliam Geffert * Breaking a Time-and-Space Barrier in Constructing Full-Text Indices, Wing-Kai Hon and Kunihiko Sadakane and Wing-Kin Sung * I/O-Efficient Strong Connectivity and Depth-First Search for Directed Planar Graphs, Lars Arge and Norbert Zeh * The Cost of Cache-Oblivious Searching, Michael A. Bender and Gerth St\o{}lting Brodal and Rolf Fagerberg and Dongdong Ge and Simai He and Haodong Hu and John Iacono and Alejandro L\'{o}pez-Ortiz * Tight Lower Bounds for the Distinct Elements Problem, Piotr Indyk and David Woodruff SESSION 7: 10:50am - 12:10pm, Chair: Daniele Micciancio * Hardness of Approximating the Shortest Vector Problem in High L_p Norms, Subhash Khot * More on average case vs approximation complexity, Michael Alekhnovich * On Worst-Case to Average-Case Reductions for NP Problems, Andrej Bogdanov and Luca Trevisan * On the Rank of Cutting Planes Proof-Systems and the Role of Expansion, Josh Buresh-Oppenheim and Nicola Galesi and Shlomo Hoory and Avner Magen and Toniann Pitassi Lunch (Provided) Afternoonu SESSION 8: 1:40pm - 3:00pm, Chair: Paul Beame * The resolution complexity of random constraint satisfaction problems, Michael Molloy and Mohammad Salavatipour * Algorithms and Complexity Results for sharpSAT and Bayesian Inference, Fahiem Bacchus and Shannon Dalmao and Toniann Pitassi * Linear Upper Bounds for Random Walk on Small Density Random 3-CNFs, Mikhail Alekhnovich and Eli Ben-Sasson * On the Maximum Satisfiability of Random Formulas, Dimitris Achlioptas and Assaf Naor and Yuval Peres SESSION 9: 3:25pm - 4:45pm, Chair: Ran Canetti * Logics for reasoning about cryptographic constructions, Russell Impagliazzo and Bruce M. Kapron * Lower Bounds for Non-Black-Box Zero Knowledge, Boaz Barak, Yehuda Lindell, Salil Vadhan * General Composition and Universal Composability in Secure Multiparty Computation, Yehuda Lindell * Bounded-Concurrent Secure Two-Party Computation in a Constant Number of Rounds, Rafael Pass and Alon Rosen SESSION 10: 5:10pm - 6:30pm, Chair: Avi Wigderson * Solving Sparse, Symmetric, Diagonally-Dominant, Linear Systems in Time O(m^1.31), Daniel Spielman and Shang-Hua Teng * Separating the Power of Monotone Span Programs over Different Fields, Amos Beimel and Enav Weinreb * A group-theoretic approach to fast matrix multiplication, Henry Cohn and Christopher Umans * Representing Boolean Functions by Symmetric Polynomials, Nayantara Bhatnagar and Parikshit Gopalan and Richard J. Lipton ------------------------------------------------------------------------ Tuesday October 14th 2003 Morning SESSION 11: 8:45 am - 10:25 am, Chair: Madhu Sudan * Smoothening Helps: A Probabilistic Analysis of the Multi-Level Feedback Algorithm, Luca Becchetti and Stefano Leonardi and Alberto Marchetti-Spaccamela and Guido Schaefer and Tjark Vredeveld * Stability and Efficiency of a Random Local Load Balancing Protocol, Aris Anagnostopoulos and Adam Kirsch and Eli Upfal * Gossip-Based Computation of Aggregate Information, David Kempe and Alin Dobra and Johannes Gehrke * Broadcasting Algorithms in Radio Networks with Unknown Topology, Artur Czumaj and Wojciech Rytter * Switch Scheduling via Randomized Edge Coloring, Gagan Aggarwal and Rajeev Motwani and Devavrat Shah and An Zhu SESSION 12: 10:50am - 12:10pm, Chair: Dana Ron * On the Impossibility of Dimension Reduction in $\ell_1$, Bo Brinkman and Moses Charikar * Clustering with Qualitative Information, Moses Charikar and Venkatesan Guruswami and Anthony Wirth * Bounded geometries, fractals, and low--distortion embeddings, Anupam Gupta and Robert Krauthgamer and James R. Lee * On Levels in Arrangements of Curves, II: A Simple Inequality and Its Consequences, Timothy M. Chan Lunch (Provided) Afternoon SESSION 13: 1:40pm - 2:20pm, Chair: Manindra Agarwal * The complexity of homomorphism and constraint satisfaction problems seen from the other side, Martin Grohe * Towards a dichotomy theorem for the Counting Constraint Satisfaction Problem, Andrei A. Bulatov and Victor Dalmau SESSION 14: 2:40pm - 4:00pm, Chair: Monika Henzinger * Towards a Characterization of Truthful Combinatorial Auctions, Ron Lavi and Ahuva Mu'alem and Noam Nisan * Strategy Proof Mechanisms via Primal-Dual Algorithms, Martin Pal and Eva Tardos * The Value of Knowing a Demand Curve: Bounds on Regret for On-Line Posted-Price Auctions, Robert Kleinberg and Tom Leighton * Approximation Via Cost-Sharing: A Simple Approximation Algorithm for the Multicommodity Rent-or-Buy Problem, Anupam Gupta and Amit Kumar and Martin Pal and Tim Roughgarden SESSION 15: 4:20pm - 5:40pm, Chair: Dana Randall * The Ising model on trees: Boundary conditions and mixing time, Fabio Martinelli and Alistair Sinclair and Dror Weitz * Logconcave Functions: Geometry and Efficient Sampling Algorithms, Laszlo Lovasz and Santosh Vempala * Simulated Annealing in Convex Bodies and an O*(n^4) Volume Algorithm, Laszlo Lovasz and Santosh Vempala * A Non-Markovian Coupling for Randomly Sampling Colorings, Thomas P. Hayes and Eric Vigoda