FOCS 2002

The 43rd Annual IEEE Symposium on Foundations of Computer Science

Vancouver, Canada

November 16-19, 2002


    9:30am - 10:00am - Coffee Break

    TUTORIAL 1:   10:00am - 12:00 pm, Chair: Venkatesan Guruswami

    Oded Goldreich: Zero-Knowledge

Lunch (on your own)

    TUTORIAL 2:   1:45pm - 3:45 pm,  Chair: Yuval Rabani

    Eva Tardos:   Approximation Algorithms

    3:45pm - 4:15pm - Coffee Break

    TUTORIAL 3:   4:15pm-6:15pm,     Chair: Omer Reingold

    Salil Vadhan:  Randomness Extractors

19:00-21:00  Welcome Reception

  • Workshop on Algorithms and Models for the Web-Graph



    CHAIR Venkatesan Guruswami

    8:55   Locally Testable Codes and PCPs of Almost-Linear Length,
    by Oded Goldreich and Madhu Sudan

    9:20   Hardness Results for Coloring 3-Colorable 3-Uniform Hypergraphs,
    by Subhash Khot

    9:45   The Hardness of 3-Uniform Hypergraph Coloring,
    by Irit Dinur, Oded Regev, and Clifford Smyth

    CHAIR Yuval Rabani

    8:30   Minimizing Congestion in General Networks,
    by Harald R\"acke 

    8:55   Small Induced Universal Graphs and Compact Implicit Graph Representations,
    by Stephen Alstrup and Theis Rauhe

    9:20   Deterministic Broadcasting Time in Radio Networks of Unknown Topology,
    by Dariusz Kowalski and Andrzej Pelc

    9:45   Explicit Unique-Neighbor Expanders,
    by Noga Alon and Michael Capalbo

    10:10-10:30 BREAK


    CHAIR Ronitt Rubinfeld

    10:30  Abstract Combinatorial Programs and Efficient Property Testers,
    by Artur Czumaj and Christian Sohler

    10:55  A Linear Lower Bound on the Query Complexity of Property Testing,
    by Andrej Bogdanov, Kenji Obata, and Luca Trevisan

    11:20  Testing Juntas,
    by Eldar Fischer, Guy Kindler, Dana Ron, Shmuel Safra, and Alex Samorodnitsky

    11:45  A Spectral Algorithm for Learning Mixtures of Distributions,
    by Santosh Vempala and Grant Wang

    CHAIR Bernard Chazelle

    10:30  Equivalence between Priority Queues and Sorting,
    by Mikkel Thorup

    10:55  Integer Sorting in O(n\sqrt{\log\log n}) Expected Time and Linear Space,
    by Yijie Han and Mikkel Thorup

    11:20  Implicit B-trees: New Results for the Dictionary Problem,
    by G. Franceschini, R. Grossi, J.I. Munro, and L. Pagli

    11:45  An Inverse-Ackermann Style Lower Bound for MST Verification Queries,
    by Seth Pettie

    12:10-2:00 LUNCH


    CHAIR Ronitt Rubinfeld

    2:00   PAC = PAExact and Other Equivalent Models in Learning,
    by Nader Bshouty and Dmitry Gavinsky

    2:25   Learning Intersections and Thresholds of Halfspaces,
    by Adam Klivans, Ryan O'Donnell, and Rocco Servedio

    2:50   On-line Transductive Confidence Machines are Well-Calibrated,
    by Vladimir Vovk

    3:15   Learning a Hidden Matching,
    by Noga Alon, Richard Beigel, Simon Kasif, Steven Rudich, and Benny Sudakov

    CHAIR Piotr Indyk

    2:00   An Information Statistics Approach to Data Stream and Communication Complexity,
    by Ziv Bar-Yossef, T.S. Jayram, Ravi Kumar, and D. Sivakumar

    2:25   Static Optimality Theorem for External Memory String Access,
    by V. Ciriani, P. Ferragina, F. Luccio, and S. Muthukrishnan

    2:50   A Simple Algorithmic Characterization of Uniform Solvability
    by Eli Gafni

    3:15   Correlation Clustering,
    by Nikhil Bansal, Avrim Blum, and Shuchi Chawla

    3:40-4:15 BREAK


    CHAIR Dan Spielman

    4:15   Decoding Turbo-Like Codes in Polynomial Time with Provably Good
    Error-Correcting Performance via Linear Programming,
    by Jon Feldman and David R. Karger

    4:40   Breaking the O(n^{1/(2k-1)}) Barrier for Information-Theoretic
    Private Information Retrieval,
    by Amos Beimel, Yuval Ishai, Eyal Kushilevitz, and Jean-Francois Raymond

    5:05   LT Codes,
    by Michael Luby

    CHAIR Edith Cohen

    4:15   Graphs with Tiny Vector Chromatic Numbers and Huge Chromatic Numbers,
    by Uriel Feige, Michael Langberg, and Gideon Schechtman

    4:40   Scheduling over a Time-Varying User-Dependent Channel with
    Applications to High Speed Wireless Data,
    by Matthew Andrews and Lisa Zhang

    5:05   On-line End-to-End Congestion Control,
    by Naveen Garg and Neal E. Young

    8:30   Business Meeting



    CHAIR David Shmoys

    8:55   Proving Integrality Gaps without Knowing the Linear Program,
    by Sanjeev Arora, Bela Bollobas, Laszlo Lovasz

    9:20   Dependent Rounding in Bipartite Graphs
    by Rajiv Gandhi, Samir Khuller, Srinivasan Parthasarathy, Aravind Srinivasan

    9:45   A Constant-Factor Approximation Algorithm for the
    Multicommodity Rent-or-Buy Problem,
    by Amit Kumar, Anupam Gupta, and Tim Roughgarden

    CHAIR Tal Rabin

    8:30   Constant-Round Coin-Tossing With a Man in the Middle or Realizing
    the Shared Random String Model,
    by Boaz Barak

    8:55   Generalized Compact Knapsacks, Cyclic Lattices, and Efficient
    One-Way Functions from Worst-Case Complexity Assumptions,
    by Daniele Micciancio

    9:20   Concurrent Zero Knowledge with Logarithmic Round Complexity,
    by Manoj M. Prabhakaran, Alon Rosen, and Amit Sahai

    9:45   On the (non)Universality of the One-Time Pad,
    by Yevgeniy Dodis and Joel Spencer

    10:10-10:30 BREAK


    CHAIR Yuval Rabani
    10:30  Market Equilibrium via a Primal-Dual-Type Algorithm,
    by Nikhil Devanur, Christos H. Papadimitriou, Amin Saberi, and Vijay Vazirani

    10:55  Optimal Auctions are Hard,
    by Amir Ronen and Amin Saberi

    11:20  Auctions with Severely Bounded Communication,
    by Liad Blumrosen and Noam Nisan

    11:45  Nash Equilibria in Competitive societies, with Applications
    to Facility Location, Traffic Routing and Auctions,
    by Adrian Vetta

    CHAIR Omer Reingold

    10:30  Privacy and Interaction in Quantum Communication Complexity
    and a Theorem about the Relative Entropy of Quantum States,
    by Rahul Jain, Jaikumar Radhakrishnan, and Pranab Sen

    10:55  Linear Diophantine Equations over Polynomials and
    Soft Decoding of Reed-Solomon Code,
    by Michael Alekhnovich

    11:20  Authentication of Quantum States,
    by Howard Barnum, Claude Crepeau, Daniel Gottesman, Adam Smith, and Alain Tapp

    11:45  Limits on the Power of Quantum Statistical Zero-Knowledge,
    by John Watrous

    12:10-2:00 LUNCH


    CHAIR David Shmoys

    2:00   Protocols and Impossibility Results for Gossip-Based Communication Mechanisms,
    by David Kempe and Jon Kleinberg

    2:25   Covering Problems with Hard Capacities,
    by Julia Chuzhoy and Joseph (Seffi) Naor

    2:50   Packing 2-Dimensional Bins in Harmony,
    by Alberto Caprara

    3:15   Fast Approximation Algorithms for Fractional Steiner Forest and Related Problems,
    by Naveen Garg and Rohit Khandekar

    CHAIR Dorit Aharonov

    2:00   Quantum Lower Bounds for the Collision and the Element Distinctness Problems,
    by Yaoyun Shi

    2:25   Quantum Computation and Lattice Problems,
    by Oded Regev

    2:50   On the Decidability of Self-Assembly of Infinite Ribbons,
    by Leonard Adleman, Jarkko Kari, Lila Kari, and Dustin Reishus

    3:15   The Parameterized Complexity of Counting Problems,
    by Joerg Flum and Martin Grohe

    3:40-4:15 BREAK


    CHAIR Bernard Chazelle

    4:15   Dimension Reduction in the L1 Norm,
    by Moses Charikar and Amit Sahai

    4:40   On Approximating the Radii of Point Sets in High Dimensions,
    by Kasturi Varadarajan, S. Venkatesh, and Jiawei Zhang

    5:05   Low-Dimensional Linear Programming with Violations,
    by Timothy M. Chan

    CHAIR Maria Bonet

    4:15   Bounded-Depth Frege Lower Bounds for Weaker Pigeonhole Principles,
    by Josh Buresh-Oppenheim, Paul Beame, Toniann Pitassi,
    Ran Raz, and Ashish Sabharwal

    4:40   Satisfiability, Branch-width and Tseitin Tautologies,
    by Michael Alekhnovich and Alexander A. Razborov

    5:05   A Switching Lemma for Small Restrictions and Lower Bounds for
    for k-DNF Resolution,                                      
    by Nathan Segerlind, Sam Buss, Russell Impagliazzo

    9:00PM  PRIMES is in P,
    Special talk by Manindra Agrawal



    CHAIR Piotr Indyk

    8:55   Dynamic Planar Convex Hull,
    by Gerth Stolting Brodal and Riko Jacob

    9:20   Optimal System of Loops on an Orientable Surface,
    by Eric Colin de Verdiere and Francis Lazarus

    9:45   The Partition Technique for Overlays of Envelopes,
    by Vladlen Koltun and Micha Sharir

    CHAIR Anna Gal

    8:30   A Dichotomy Theorem for Constraints on a Three-Element Set,
    by Andrei A. Bulatov

    8:55   Lower Bounds on the Bounded Coefficient Complexity of Bilinear Maps,
    by Peter Buergisser and Martin Lotz

    9:20   Power from Random Strings,
    by Eric Allender, Harry Buhrman, Michal Koucky,
    Dieter van Melkebeek, and Detlef Ronneburger

    9:45    Improved Dynamic Reachability Algorithms for Directed Graphs,
    by Liam Roditty and Uri Zwick

    10:10-10:30 BREAK


    CHAIR Claire Kenyon
    10:30  Conflict-Free Colorings of Simple Geometric Regions
    with Applications to Frequency Assignment in Cellular Networks
    by Guy Even, Zvi Lotker, Dana Ron, and Shakhar Smorodinsky

    10:55  Global Information from Local Observation,
    by Itai Beniamini and Laszlo Lovasz

    11:20  Rapidly Mixing Markov Chains for Sampling Contingency Tables
    with a Constant Number of Rows,
    by Mary Cryan, Martin Dyer, Leslie Ann Goldberg, Mark Jerrum and
    Russell Martin

    11:45  Spectral Gap and log-Sobolev Constant for Balanced Matroids,
    by Mark R. Jerrum and Jung-Bae Son

    CHAIR Anna Gal

    10:30  Random Lattices and a Conjectured 0-1 Law about their Polynomial
    Time Computable Properties,
    by Miklos Ajtai

    10:55  Graph Isomorphism is in SPP,
    by V. Arvind and Piyush P Kurur

    11:20  Kolmogorov's Structure Functions with an Application to the Foundations
    of Model Selection,
    by Nikolai K. Vereshchagin and Paul M.B. Vitanyi

    11:45  Forbidden Information,
    by Leonid A. Levin

    12:10-2:00 LUNCH


    CHAIR Claire Kenyon

    2:00   The 3-XORSAT Threshold (Strong Evidence in Favour of the Replica
    Method of Statistical Physics),
    by Olivier Dubois and Jacques Mandler

    2:25   The Asymptotic Order of the Random k-SAT Threshold,
    by Dimitris Achlioptas and Cristopher Moore

    2:50   On Random Symmetric Travelling Salesman Problems,
    by Alan M. Frieze

    3:15   Load Balancing with Memory,
    by Michael Mitzenmacher, Balaji Prabhakar, and Devavrat Shah