FOCS 2000 PROGRAM AND REGISTRATION INFORMATION http://www.cs.cmu.edu/~FOCS2000 Deadline for early registration is OCTOBER 16 --------------------------------------------------------- The 41st Annual IEEE Computer Society Conference on Foundations of Computer Science 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 FORM (available in PostScript at http://www.cs.cmu.edu/~FOCS2000) Name: Affiliation: Address: E-mail: Phone: Dietary restrictions: Kosher / Vegetarian / None Affiliation, as it should appear on the badge: Please circle one category below and fill in your membership number if appropriate: # Registration fees until 10/16 after 10/16 ACM, SIGACT, IEEE or EATCS member 330 390 Author 330 390 Student 110 130 Other 420 480 Machtey Fund contribution: Total registration: To pay by Visa, Mastercard or Discover, provide the name that appears on the card, the billing address of this card, and the signature of the card holder. Name: Address: Card Type: Card Number: Expiration Date: Signature: I agree to pay the above total amount according to card issuer agreement. Send to: Joyce Akhtarkhavari, Attn: FOCS 2000, Department of Computer Science, University of California, Riverside, CA 92521. Fax: 909-787-4643. ======================================================== 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. ========================================================= 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. Kolaitis 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. ========================================================== CORPORATE SUPPORT FOCS 2000 gratefully acknowledges financial support from IBM Research and Akamai Technologies.