Sunday October 14th 2001

Tutorials Day

   TUTORIAL 1:  10:00am - 12:00 pm, Chair: Jon Kleinberg

   Christos Papadimitriou:
       Game Theory and Mathematical Economics: A Theoretical Computer Scientist's Introduction

Lunch (on your own)
 

   TUTORIAL 2:   1:50pm - 3:50 pm, Chair: D. Sivakumar

    Piotr Indyk:
       Algorithmic Applications of Geometric Embeddings

   TUTORIAL 3:   4:10pm-6:10pm,  Chair: Daniele Micciancio

    Madhu Sudan:
         Coding Theory

Welcome Reception  7:00 pm - 8:30pm
 

Monday October 15th 2001

 Morning

  SESSION 1:  8:30 am - 10:10 am, Chair: Moses Charikar

    Almost Tight Upper Bounds for Vertical Decompositions in Four Dimensions,
        Vladlen Koltun - Machtey Award Co-winner
    Approximate Shape fitting via Linearization,
        Sariel Har-Peled and Kasturi R. Varadarajan
    On the Complexity of Many Faces in Arrangements of Circles,
        Pankaj K. Agarwal and Boris Aronov and Micha Sharir
    Clustering Motion,
        Sariel Har-Peled
    A Replacement for Voronoi Diagrams of Near Linear Size,
        Sariel Har-Peled

  SESSION 2:   10:40am - 12:00pm, Chair: Cynthia Dwork

    How to Go Beyond The Black-Box Simulation Barrier,
        Boaz Barak - Machtey Award Co-winner
    Resettably-Sound Zero-Knowledge and its Applications,
        Boaz Barak, Oded Goldreich, Shafi Goldwasser and Yehuda Lindel
    On the Impossibility of Basing Trapdoor Functions on Trapdoor Predicates,
        Yael Gertner, Tal Malkin and Omer Reingold
    Universally Composable Security: A New Paradigm for Cryptographic Protocols,
        Ran Canetti

  Lunch (Provided)

 Afternoon

  SESSION 3:   1:30pm - 2:50pm, Chair: Jon Kleinberg

    Routing Issues in MPLS (Or, How to Travel with a Pez Dispenser),
        Anupam Gupta, Amit Kumar and Rajeev Rastogi
    Simple Routing Strategies for Adversarial Systems,
        Baruch Awerbuch, Petra Berenbrink, Andre Brinkmann and Christian Scheideler
    Source Routing and Scheduling in Packet Networks,
        M. Andrews, A. Fernandez, A. Goel and L. Zhang
    The Natural Work-Stealing Algorithm is Stable,
        Petra Berenbrink, Tom Friedetzky and Leslie Ann Goldberg

  SESSION 4:  3:10pm - 4:30pm, Chair: Alistair Sinclair

    Lower Bounds for Polynomial Calculus: Non-Binomial Case,
        Michael Alekhnovich and Alexander Razborov
    Counting Axioms do not Polynomially Simulate Counting Gates,
        Russell Impagliazzo and Nathan Segerlind
    Resolution is Not Automatizable Unless W[P] is Tractable,
        Michael Alekhnovich and Alexander Razborov
    "Planar" Tautologies, Hard for Resolution,
        Stefan Dantchev and Søren Riis

  SESSION 5:  4:50pm - 6:10pm, Chair: Susanne Albers

    Planar Graphs, Negative Weight Edges, Shortest Paths and Near Linear Time,
        Jittat Fakcharoenphol and Satish Rao
    Compact Oracles for Reachability and Approximate Distances in Planar Digraphs,
        Mikkel Thorup
     Vickrey Pricing in Network Routing: Fast Payment Computation,
         John Hershberger and Subhash Suri
    Fully Dynamic All Pairs Shortest Paths with Real Edge Weights,
        Camil Demetrescu and Giuseppe F. Italiano

FOCS 2001 Business Meeting 9:00 pm - 10:00 pm

Tuesday October 16th 2001

  Morning

  SESSION 6:  8:30 am - 10:10 am, Chair: D. Sivakumar

    Informational Complexity and the Direct Sum Problem for Simultaneous Message Complexity,
        Amit Chakrabarti, Yaoyun Shi, Anthony Wirth and Andrew Yao
    How Powerful is Adiabatic Quantum Computation?,
        Wim van Dam, Mike Mosca and Umesh Vazirani
    Lower Bounds for Quantum Communication Complexity,
        Hartmut Klauck
    The Confluence of Ground Term Rewriting Systems is Decidable in Polynomial Time,
        H. Comon, G. Godoy and R. Nieuwenhuis
    On the Average-Case Hardness of CVP,
        Jin-Yi Cai

  SESSION 7:  10:40am - 12:00pm, Chair: Susanne Albers

    Approximating Directed Multicuts,
        Joseph Cheriyan, Howard Karloff and Yuval Rabani
    Facility Location with Nonuniform Hard Capacities,
        Martin Pal, Eva Tardos and Tom Wexler
    An Iterative Rounding 2-Approximation Algorithm for the Element Connectivity Problem,
        Lisa Fleischer, Kamal Jain and David P. Williamson
    Approximation Algorithms for the Job Interval Selection Problem and Related Scheduling Problems,
        Julia Chuzhoy, Rafail Ostrovsky and Yuval Rabani

 Lunch (Provided)

 Afternoon

   SESSION 8:  1:30pm - 2:50pm, Chair: Peter Bro Miltersen

    Lower Bounds for Matrix Product,
        Amir Shpilka
    Deterministic Computation of the Frobenius Form,
        Arne Storjohann
    The Complexity of Factors of Multivariate Polynomials,
        Peter Burgisser
    Linear-time Recognition of Circular-arc Graphs,
        R.M. McConnell

   SESSION 9:   3:10pm - 4:30pm, Chair: Moses Charikar

    Ramsey Type Theorems for Metric Spaces and their Application for Metrical Task Systems,
        Yair Bartal, Bela Bollobas and Manor Mendel
    Designing Networks Incrementally,
        Adam Meyerson,  Kamesh Munagala and Serge Plotkin
    Sorting and Selection with Structured Costs,
       Anupam Gupta and Amit Kumar
    Online Facility Location,
       Adam Meyerson

  SESSION 10:   4:50pm - 6:10pm, Chair: Moni Naor

    Testing Subgraphs in Large Graphs,
        Noga Alon
    Testing Random Variables for Independence and Identity,
        Tugkan Batu, Lance Fortnow, Eldar Fischer, Ravi Kumar and Ronitt Rubinfeld and Patrick White
    Fast Monte-Carlo Algorithms for Approximating Matrix Multiplication,
        Petros Drineas and Ravi Kannan
    Three Theorems regarding Testing Graph Properties,
        Oded Goldreich and Luca Trevisan

Wednesday October 17th 2001

 Morning

  SESSION 11:   8:30 am - 10:10 am, Chair: James Aspnes

    Designing Networks for Selfish Users is Hard,
        Tim Roughgarden
    Truthful Mechanisms for One-Parameter Agents,
        Aaron Archer and Eva Tardos
    Building Low-diameter P2P Networks,
        Gopal Pandurangan, Prabhakar Raghavan and Eli Upfal
    Web Search through Hub Synthesis,
        Dimitris Achlioptas, Amos Fiat, Anna Karlin and Frank McSherry
    Random Evolution in Massive Graphs,
        William Aiello, Fan Chung and Linyuan Lu

  SESSION 12:    10:40am - 12:00pm, Chair: Madhu Sudan

    Tight Approximation Results for General Covering Integer Programs,
        Stavros G. Kolliopoulos and Neal E. Young
    Spectral Partitioning of Random Graphs,
        Frank McSherry
    Sequential and Parallel Algorithms for Mixed Packing and Covering,
        Neal E. Young
    Unique Sink Orientations of Cubes,
        Tibor Szabó and Emo Welzl

 Lunch (Provided)

 Afternoon

   SESSION 13:   1:30pm - 2:50pm, Chair: Alistair Sinclair

    Arc Disjoint Paths in Expander Digraphs,
        Tom Bohman and Alan Frieze
    Glauber Dynamics on  Trees and Hyperbolic Graphs,
        Claire Kenyon, Elchanan Mossel and Yuval Peres
    Randomly Colouring Graphs with Lower Bounds on girth and Maximum Degree,
        Martin Dyer and Alan Frieze
    Distributions on level-sets with Applications to Approximation Algorithms,
        Aravind Srinivasan

   SESSION 14:   3:10pm - 4:10pm, Chair: Daniele Micciancio

    Improved Inapproximability Results for MaxClique, Chromatic Number and Approximate Graph Coloring,
        Subhash Khot
    Query efficient PCPs with perfect completeness,
        Johan Hastad and Subhash Khot
    S_2^p \subseteq ZPP^{NP},
         Jin-Yi Cai

   SESSION 15:   4:30pm - 5:50pm, Chair: Salil Vadhan

    Semi-direct Product in Groups and Zig-zag Product in Graphs: Connections and Applications,
        Noga Alon, Alexander Lubotzky and Avi Wigderson
    Extractors from Reed-Muller Codes,
        Amnon Ta-Shma, David Zuckerman and Shmuel Safra
    Simple Extractors for All Min-Entropies and a New Pseudo-Random Generator,
        Ronen Shaltiel and Christopher Umans
    Expander-based Constructions of Efficiently Decodable Codes,
        Venkatesan Guruswami and Piotr Indyk