FOCS 2000 program and registration info

Wed Sep 13 11:32:10 PDT 2000

                   FOCS 2000

   The 41 st Annual IEEE Computer Society 
 Conference on Foundations of Computer Science

       http://www.cs.cmu.edu/~FOCS2000

         November 12-14, 2000
       Redondo Beach, California

    Sponsored by the IEEE Computer Society 
     Technical Committee on Mathematical 
         Foundations of Computing

      In cooperation with ACM SIGACT

---------------------------------------------------------

REGISTRATION

The deadline for early registration is OCTOBER 16.

Instructions on how to register by fax or mail can be
found at http://www.cs.cmu.edu/~FOCS2000.

The registration desk will be open from 6 pm to 10 pm on
Saturday, and during the day on Sunday and Monday.

---------------------------------------------------------

HOTEL

The conference will take place at the Crowne Plaza
Hotel, 300 N. Harbor Drive, Redondo Beach, CA 90277, USA.

A block of rooms has been reserved in the hotel
at the special rate of $125 per day, single or double.
To obtain the room at this price, you need to make a
reservation by OCTOBER 16.

To reserve a room you can

    * call the hotel at 310-318-8888 or 800-368-9760, or
    * fill the hotel reservation form at 
           http://www.cs.cmu.edu/~FOCS2000
      and fax it to the hotel at 310-376-1930.

If you make the reservation by phone, please specify that
you request the special rate for IEEE FOCS 2000.

---------------------------------------------------------

CORPORATE SUPPORT

FOCS 2000 gratefully acknowledges financial support from
IBM Research and Akamai Technologies.

=========================================================
               CONFERENCE PROGRAM
=========================================================

SATURDAY, NOVEMBER 11, 2000

Welcome Reception 7:00 pm - 8:30pm

----------------------------------------------------------

SUNDAY, NOVEMBER 12, 2000

SESSION 1: 8:30 am - 10:10 am, Chair: David Zuckerman

Entropy waves, the zig-zag graph product, and new
constant-degree expanders and extractors,
O. Reingold, S. Vadhan, and A. Wigderson

Universality and tolerance,
N. Alon, M. Capalbo, Y. Kohayakawa, V. Rodl, A. Rucinski,
and E. Szemeredi

Extracting randomness via repeated condensing,
O. Reingold, R. Shaltiel, and A. Wigderson

Extracting randomness from samplable distributions,
L. Trevisan and S. Vadhan

Pseudorandom generators in propositional proof complexity,
M. Alekhnovich, E. Ben-Sasson, A.A. Razborov,
and A. Wigderson

SESSION 2:  10:30am - 12:10pm, Chair: David Williamson

Random graph models for the web graph,
R. Kumar, P. Raghavan, S. Rajagopalan, D. Sivakumar,
A. Tomkins, and E. Upfal

Optimization problems in congestion control,
R. Karp, E. Koutsoupias, C. Papadimitriou, and S. Shenker

Fairness measures for resource allocation,
A. Kumar and J. Kleinberg

On the approximability of trade-offs and optimal access
of web sources,
C.H. Papadimitriou and M. Yannakakis

How bad is selfish routing?,
T. Roughgarden and E. Tardos

SESSION 3: 1:30pm - 2:50pm, Chair: Sanjeev Arora

A polylogarithmic approximation of the minimum bisection,
U. Feige and R. Krauthgamer

Approximability and in-approximability results for no-wait
 shop scheduling problems,
M. Sviridenko and G. Woeginger

Nested graph dissection and approximation algorithms,
S. Guha

Approximating the single source unsplittable min-cost flow
problem,
M. Skutella

SESSION 4: 3:10pm - 4:30pm, Chair: Michael Sipser

Hardness of approximate hypergraph coloring,
V. Guruswami, J. Hastad, and M. Sudan

"Soft-decision" decoding of Chinese remainder codes,
V. Guruswami, A. Sahai, and M. Sudan

Super-linear time-space tradeoff lower bounds for
randomized computation,
P. Beame, M. Saks, X. Sun, and E. Vee

On the hardness of graph isomorphism,
J. Toran

SESSION 5: 4:50pm - 6:10pm, R. Ravi

Stable distributions, pseudorandom generators, embeddings
and data stream computation,
P. Indyk

New data structures for orthogonal range searching,
S. Alstrup, G.S. Brodal, and T. Rauhe

Nearly optimal expected-case planar point location,
S. Arya, T. Malamatos and D.M. Mount

On levels in arrangements of curves,
T.M. Chan

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

----------------------------------------------------------

MONDAY, NOVEMBER 13, 2000

SESSION 6: 8:30 am - 10:10 am, Chair: Avrim Blum

Detecting a network failure,
J. Kleinberg

Testing of clustering,
N. Alon, S. Dar, M. Parnas, and D. Ron

Testing of functions that have small width branching
programs,
I. Newman

Testing that distributions are close,
T. Batu, L. Fortnow, R. Rubinfeld, W.D. Smith,
and P. White

Using upper confidence bounds for online learning,
P. Auer

SESSION 7: 10:30am - 12:10pm, Chair: Joe Kilian

Zaps and their applications
C. Dwork and M. Naor

Randomizing polynomials: a new representation with
applications to round-efficient secure computation,
Y. Ishai and E. Kushilevitz

Lower bounds on the efficiency of generic cryptographic
constructions,
R. Gennaro and L. Trevisan

Concurrent oblivious transfer,
J. Garay and P. MacKenzie

The relationship between public key encryption and
oblivious transfer,
Y. Gertner, S. Kannan, T. Malkin, O. Reingold,
and M. Viswanathan

SESSION 8: 1:30pm - 2:50pm, Chair: Leonard Schulman

The online median problem,
R. Mettu and G. Plaxton

Polynomial time approximation schemes for geometric
k-clustering,
R. Ostrovsky and Y. Rabani

Clustering data streams,
S. Guha, N. Mishra, R. Motwani, and L. O'Callaghan

On clusterings: good, bad and spectral,
R. Kannan, S. Vempala and A. Vetta

SESSION 9: 3:10pm - 4:30pm, Chair: Leonard Schulman

Fully dynamic transitive closure: breaking through
the O(n^2) barrier,
C. Demetrescu and G.F. Italiano

Opportunistic data structures with applications,
P. Ferragina and G. Manzini

Cache-oblivious B-trees,
M.A. Bender, E.D. Demaine, and M. Farach-Colton

Using expander graphs to find vertex connectivity,
H.N. Gabow

SESSION 10: 4:50pm - 6:10pm, Chair: M. Szegedy

On the boundary complexity of the union of fat triangles,
J. Pach and G. Tardos

Straighting polygonal arcs and convexifying polygonal
cycles,
R. Connelly, E.D. Demaine and G. Rote

A combinatorial approach to planar non-colliding robot
arm motion planning,
I. Streinu

Topological persistence and simplification,
H. Edelsbrunner, D. Letscher, and A. Zomorodian

Banquet and Knuth Prize Lecture 7:00 pm

----------------------------------------------------------

TUESDAY, NOVEMBER 14, 2000

SESSION 11: 8:30 am - 10:10 am, Chair: Leslie Goldberg

The cover time, the blanket time, and the Matthews bound,
J. Kahn, J.H. Kim, L. Lovasz, and V. H. Vu

The product replacement algorithm is polynomial,
I. Pak

Efficient algorithms for universal portfolios,
A. Kalai, and S. Vempala

Sampling adsorbing staircase walks using a new Markov
chain decomposition method,
R. Martin and D. Randall

The randomness recycler:  a new technique for perfect
sampling,
J.A. Fill and M.L. Huber

SESSION 12: 10:30am - 12:10pm, Chair: Umesh Vazirani

An improved quantum Fourier transform algorithm and
applications,
L. Hales and S. Hallgren

Fast parallel circuits for the quantum Fourier transform,
R. Cleve and J. Watrous

Succinct quantum proofs for properties of finite groups,
J. Watrous

Private quantum channels,
A. Ambainis, M. Mosca, A. Tapp, and R. de Wolf

The quantum complexity of set membership,
J. Radhakrishnan, P. Sen, and S. Venkatesh

SESSION 13: 1:30pm - 2:50pm, Leslie Goldberg 

Randomized rumor spreading,
R. Karp, C. Schindelhauer, S. Shenker, and B. Vocking

Fast broadcasting and gossiping in radio networks,
M. Chrobak, L. Gasieniec and W. Rytter

Linear waste of best fit bin packing on skewed
distributions,
C. Kenyon and M. Mitzenmacher

Optimal myopic algorithms for random 3-SAT,
D. Achlioptas and G.B. Sorkin

SESSION 14: 3:10pm - 4:30pm, Chair: David Williamson

Hierarchical placement and network design problems,
S. Guha, A. Meyerson, and K. Munagala

Building Steiner trees with incomplete global knowledge,
D.R. Karger and M. Minkoff

Cost-distance: two metric network design,
A. Meyerson, K. Munagala, and S. Plotkin

Combinatorial feature selection problems,
M. Charikar, V. Guruswami, R. Kumar, S. Rajagopalan,
and A. Sahai

SESSION 15: 4:50pm - 6:10pm, Michael Sipser

The common fragment of CTL and LTL,
M. Maidl

On the existence of booster types,
M. Herlihy and E. Ruppert

Existential second-order logic over graphs: charting
the tractability frontier,
G. Gottlob, P. Kolatis and T. Schwentick

Computing the determinant and Smith form of an integer
matrix,
W. Eberly, M. Giesbrecht, and G. Villard

========================================================
                  COMMITTEES
========================================================

Conference General Chair: Alok Aggarwal, IBM Research.

Program Committee Chair: Avrim Blum, Carnegie Mellon.

Program Committee: Sanjeev Arora, Avrim Blum, Faith Fich,
Leslie Ann Goldberg, Michael Goodrich, Monika Henzinger,
Joe Kilian, Yishay Mansour, R. Ravi, Leonard Schulman,
Michael Sipser, Mario Szegedy, Umesh Vazirani,
David Williamson, David Zuckerman.

Local Arrangements: Marek Chrobak and Tao Jiang,
University of California, Riverside.

-------------
The compgeom mailing lists: see
http://netlib.bell-labs.com/netlib/compgeom/readme.html
or send mail to compgeom-request at research.bell-labs.com with the line:
send readme
Now archived at http://uiuc.edu/~sariel/CG/compgeom/maillist.html.