Preliminary Program for FOCS 2003 
Saturday October 11th 2003

Tutorials Day at Radcliffe Institute for Advanced Study

TUTORIAL 1:   1:20pm - 3:20 pm, Chair: Paul Beame

Dana Randall: Mixing
Lunch (on your own)

TUTORIAL 2:  9:30am - 11:30 pm, Chair: Michael Mitzenmacher

Avrim Blum: Machine Learning: my favorite results, directions, and open problems
TUTORIAL 3:   3:50pm-5:50pm,  Chair: Avi Wigderson

Eli Upfal: 

Welcome Reception  7:00 pm - 8:30pm



Sunday October 12th 2003


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)


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


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)


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


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)


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