From vjm@alpha.cs.miami.edu Thu Aug 14 01:09:44 1997 Date: Fri, 8 Aug 1997 16:54:37 PDT From: Victor Milenkovic Reply-To: Theory-A - TheoryNet World-Wide Events , Victor Milenkovic To: THEORYNT@LISTSERV.NODAK.EDU Subject: FOCS '97 Program (text) FOCS '97 The 38th Annual IEEE Conference on the Foundations of Computer Science October 20-22, 1997 Miami Beach, Florida Sponsored by the IEEE Computer Society in cooperation with ACM SIGACT. Registration Instructions for FOCS '97 The registration fees for FOCS '97 are listed on the registration form. To qualify for the early registration fee, your registration application must be postmarked by ***FRIDAY, SEPTEMBER 19***. Refund requests will be honored until October 3. The registration fee includes the Sunday night reception, the Monday night business meeting, coffee breaks and lunches, and a copy of the proceedings. Please completely fill out the top half of the registration form. Make check or money order (in U.S. $, drawn on a U.S. bank) payable to ``IEEE - FOCS '97 Symposium,'' and send both to the address given at the bottom. For those of you who find it inconvenient to pay by check or money order, particularly those attending from outside the U.S., it is possible this year to pay by credit card. Fill out credit card information and sign, making sure that you list your name exactly as it appears on your check or credit card. The following credit cards are accepted: Visa, Mastercard, American Express. MACHTEY AWARD: The Machtey Award is presented for the most outstanding paper (or papers) written by a student or collaboration of students, as judged by the Program Committee. The award includes a grant to help defray expenses incurred in attending the Symposium. Please consider making a donation to the Machtey Award Fund so that this award tradition can be sustained. Please use a separate check for your donation. ------------------------------------------------------------------------ Registration Form for FOCS '97 Name Affiliation Street Address City State ZIP or Country & Postal code E-mail Phone Dietary restrictions: Kosher Vegetarian None Please circle one category below and fill in your membership number if appropriate: # CATEGORY FEE AFTER 9/19 ---------------------------------------------------------- ACM or SIGACT member 280 295 IEEE or EATCS member 280 295 Author or Program Committee 280 295 Student 80 100 Other 350 375 Total registration If paying registration fees by credit card please complete, using name as it appears on card: Name Credit Card Type Credit Card Number Expiration Date Signature Machtey Fund Contributions (Make separate check to Machtey Award Fund) Mail form and payment to: Victor Milenkovic Attn: FOCS '97 Registration Dept. of Math and CS University of Miami P. O. Box 249085 Coral Gables, FL 33124 ------------------------------------------------------------------------ Hotel Reservations The conference will be held at the Ramada Resort Deauville on Miami Beach, Florida. The rates for IEEE FOCS '97 are posted below. Please advise the hotel of late arrival. Reservations should be made by ***SEPTEMBER 27***. Reservations made after that will be accepted on a rate and space availability basis. Refer to IEEE FOCS '97 when making reservations to obtain the rates listed. To make your reservations by phone, call (800) 327-6656 9-5pm U.S. east coast time, or (305) 865-8511, ext. 3200, or fax (305) 865-8154. To make reservations by mail or fax, fill out the form below and send it to the address below. A deposit in the form of a check or money order for one night's stay, or credit card information and your return phone and/or fax must be included. When filling out the form, make sure that you list your name exactly as it appears on your check or credit card. The following credit cards are accepted: American Express, Diners Club, Visa, Mastercard, and Discover. Deposits will be refunded if the hotel is notified at least 72 hours before your specified arrival. ------------------------------------------------------------------------ Ramada Resort Deauville Attn: IEEE FOCS '97 Reservations 6701 Collins Avenue Miami Beach, FL 33141 Please check one: Single $79 Double $79 Triple $93 Quad $107 Arrival Date: Departure Date: Please fill out: Name Address Fax: Phone: Sharing room with If paying for deposit by credit card please complete: Credit Card Type Credit Card Number Expiration Date I authorize the Ramada Resort Deauville to charge the above account for the amount equal to one night's stay as deposit. Signature ------------------------------------------------------------------------ SUNDAY, OCTOBER 19, 1997 RECEPTION: 8:00 pm -- 11:00 pm, Ramada Resort Deauville MONDAY, OCTOBER 20, 1997 SESSION 1A: 9:00am -- 10:35am CHAIR: Monika Rauch Henzinger 9:00 Beyond Flow Decomposition Barrier. Andrew V. Goldberg (NEC, New Jersey) and Satish Rao (NEC, New Jersey). 9:25 Undirected Single Source Shortest Path in Linear Time. Mikkel Thorup (University of Copenhagen). 9:50 A Faster Deterministic Algorithm for Minimum Spanning Trees. Bernard Chazelle (Princeton University). 10:15 Flows in Undirected Unit Capacity Networks. Andrew Goldberg (NEC, New Jersey) and Satish Rao (NEC, New Jersey). SESSION 1B: 9:00am -- 10:35am CHAIR: Ronitt Rubinfeld 9:00 Randomized and Deterministic Algorithms for the Dimension of Algebraic Varieties. Pascal Koiran (Ecole normale sup\'erieure de Lyon). 9:25 Deciding Properties of Polynomials without Factoring. Tomas Sander and M. Amin Shokrollahi (University of California, Berkeley). 9:50 An Improved Algorithm for Quantifier Elimination over Real Closed Fields. Saugata Basu (New York University). 10:15 On the Power of Quantum Finite State Automata. Attila Kondacs (E\"otv\"os University, Budapest) and John Watrous (University of Wisconsin). Coffee Break: 10:35am -- 11:00am Invited Talk: 11:00am -- 12:00pm TWO DECADES OF TEMPORAL LOGIC: ACHIEVEMENTS AND CHALLENGES Amir Pnueli Weizmann Institute of Science Lunch: 12:00pm -- 1:30pm SESSION 2A: 1:30pm -- 3:05pm CHAIR: Nir Shavit 1:30 Computable Obstructions to Wait-Free Computability. John Havlicek (The University of Texas at Austin). 1:55 Reliable Cellular Automata with Self - Organization. Peter Gacs (Boston University). 2:20 Alternating-Time Temporal Logic. Rajeev Alur (University of California, Berkeley), Thomas Henzinger and Orna Kupferman. 2:45 On the Complexity of a Set-Union Problem. Richard J. Lipton, Paul J. Martino (Princeton University) and Andy Neitzke. SESSION 2B: 1:30pm -- 3:05pm CHAIR: Raimund Seidel 1:30 Succinct Representation of Balanced Parentheses, Static Trees and Planar Graphs. Ian Munro and Venkatesh Raman (Chennai Institute of Technology). 1:55 Deterministic Superimposed Coding with Applications to Pattern Matching. Piotr Indyk (Stanford University). 2:20 Optimal Suffix Tree Construction with Large Alphabets. Martin Farach (Rutgers University). 2:45 Pattern Matching with Swaps. Amihood Amir, Yonatan Aumann, Gad Landau, Moshe Lewenstein (Bar-Ilan University) and Noa Lewenstein. Coffee Break: 3:05pm -- 3:30pm SESSION 3A: 3:30pm -- 5:05pm CHAIR: Ken Clarkson 3:30 Improved Bounds for k-sets and k-th Levels. T. Dey (India Institute of Technology, Kharagpur). 3:55 Computing Integral Points in Convex Semi-algebraic Sets. Leonid Khachiyan and Lorant Porkolab (Rutgers, the State University of New Jersey). 4:20 The Computational Complexity of Knot and Link Problems. Joel Hass, Jeffrey C. Lagarias and Nicholas Pippenger (University of British Columbia). 4:45 Approximating Shortest Paths on an Nonconvex Polyhedron. Kasturi R. Varadarajan (Duke University) and Pankaj K. Agarwal. SESSION 3B: 3:30pm -- 5:05pm CHAIR: Steven Phillips 3:30 Randomized Allocation Processes. Artur Czumaj (Universit\"at-Gesamthochschule Paderborn) and Volker Stemann. 3:55 The Analysis of a List-Coloring Algorithm on a Random Graph. Dimitris Achlioptas (University of Toronto) and Michael Molloy. 4:20 Contention Resolution with Guaranteed Constant Expected Delay. Leslie Ann Goldberg and Philip D. MacKenzie (Boise State University). 4:45 Path Coupling: A Technique for Proving Rapid Mixing in Markov Chains. Russ Bubley (University of Leeds) and Martin Dyer. BUSINESS MEETING: 8:30pm -- 10:00pm TUESDAY, OCTOBER 21, 1997 SESSION 4A: 9:00am -- 10:35am CHAIR: Noam Nisan 9:00 Separation of the Monotone NC Hierarchy. Ran Raz and Pierre McKenzie (University of Montreal). 9:25 Making Nondeterminism Unambiguous. Klaus Reinhardt (Universit\"at T\"ubingen) and Eric Allender (Rutgers University). 9:50 No Feasible Interpolation for TC^0 Frege Proofs. M. Bonet, P. Pitassi (The University of Arizona), R. Raz. 10:15 Weak Random Sources, Hitting Sets, and BPP Simulations. Alexander E. Andreev, Andrea E.F. Clementi (University of Rome ``La Sapienza''), Jose' D.P. Rolim and Luca Trevisan. SESSION 4B: 9:00am -- 10:35am CHAIR: Greg Plaxton 9:00 Parallel Gaussian Elimination with Linear Work and Fill. Claudson Bornstein (Carnegie Mellon University), Bruce Maggs, Gary Miller and R. Ravi. 9:25 Exploiting Locality for Data Management in Systems of Limited Bandwidth. Bruce M. Maggs, Friedhelm Meyer auf der Heide, Berthold Vocking (Universit\"at-Gesamthochschule Paderborn) and Matthias Westermann. 9:50 General Dynamic Routing with Per-Packet Delay Guarantees of O(distance + 1 / session rate). Matthew Andrews, Antonio Fernandez, Mor Harchol-Balter (Massachusetts Institute of Technology), Tom Leighton and Lisa Zhang. 10:15 Global Optimization using Local Information with Applications to Flow Control. Yair Bartal (University of California, Berkeley), John Byers and Danny Raz. Coffee Break: 10:35am -- 11:00am Invited Talk: 11:00am -- 12:00pm CRYPTOGRAPHY AND COMPLEXITY THEORY: A MATCH MADE IN HEAVEN. Shafi Goldwasser Massachusetts Institute of Technology Lunch: 12:00pm -- 1:30pm SESSION 5A: 1:30pm -- 3:05pm CHAIR: Anna Karlin 1:30 Truly Online Paging with Locality of Reference. Amos Fiat (Duke University) and Manor Mendel. 1:55 The Competitive Analysis of Risk Taking with Applications to Online Trading. Sabah al-Binali (Columbia University). 2:20 Minimizing Flow Time Nonclairvoyantly. Bala Kalyanasundaram and Kirk Pruhs (University of Pittsburgh). 2:45 Storage Management for Evolving Databases. Jon Kleinberg, Rajeev Motwani, Prabhakar Raghavan and Suresh Venkatasubramanian (Stanford University). SESSION 5B: 1:30pm -- 3:05pm CHAIR: Uri Feige 1:30 Replication Is NOT Needed: A SINGLE Database Computational PIR. E. Kushilevitz (Technion University) and R. Ostrovsky. 1:55 Does Parallel Repetition Lower the Error in Computationally Sound Protocols? Mihir Bellare (University of California, San Diego), Russell Impagliazzo and Moni Naor. 2:20 Optimal Resilience Proactive Public Key Cryptosystems. Yair Frankel, Peter Gemmell (Sandia National Laboratories), Phil MacKenzie (Boise State University) and Moti Yung. 2:45 A Concrete Security Treatment of Symmetric Encryption. Mihir Bellare (University of California, San Diego), Anand Desai, Eron Jokipii and Phillip Rogaway (University of California, Davis). Coffee Break: 3:05pm -- 3:30pm SESSION 6A: 3:30pm -- 5:05pm CHAIR: Madhu Sudan 3:30 A 7/8-eps Approximation Algorithm for MAX 3SAT. Howard Karloff and Uri Zwick (University of California, Berkeley). 3:55 Vertex Cover Eludes the Schrijver Function. Jens Lagergren (Stockholm University) and Alexander Russell. 4:20 Improved Approximations for Edge - Disjoint Paths, Unsplittable Flow, and Related Routing Problems. Aravind Srinivasan (National University of Singapore). 4:45 Improved Approximation Algorithms for Unsplittable Flow Problems. Stavros G. Kolliopoulos (Dartmouth College) and Clifford Stein. SESSION 6B: 3:30pm -- 5:05pm CHAIR: Hugo Krawczyk 3:30 Lower Bounds for the Signature Size of Incremental Schemes. M. Fischlin (Johann Wolfgang Goethe Universit\"at, Frankfurt am Main). 3:55 A Complete Promise Problem for Statistical Zero-Knowledge. Amit Sahai (Massachusetts Institute of Technology) and Salil Vadhan. 4:20 Number-Theoretic Constructions of Efficient Pseudo-Random Functions and Other Cryptographic Primitives. Moni Naor and Omer Reingold (Weizmann Institute of Science). 4:45 An Improved Worst-Case to Average-Case Connection for Lattice Problems. Jin-yi Cai (University of Buffalo) and Ajay P. Nerurkar. WEDNESDAY, OCTOBER 22, 1997 SESSION 7A: 9:00am -- 10:10am CHAIR: Christos Papadimitriou 9:00 Finding an Even Hole in a Graph. M. Conforti, G. Cornuejols, A. Kapoor and K. Vuskovic (University of Kentucky). 9:25 Edge-Connectivity Augmentation Preserving Simplicity. J. Bang-Jensen and T. Jordan (Odense University, Denmark). 9:50 Hamiltonian Cycles in Solid Grid Graphs. Christopher Umans (University of California, Berkeley) and William Lenhart. SESSION 7B: 9:00am -- 10:10am CHAIR: Ravi Kannan 9:00 A Random Sampling based Algorithm for Learning the Intersection of Half-spaces. Santosh Vempala (Carnegie Mellon University). 9:25 Learning Noisy Perceptrons by a Perceptron in Polynomial Time. E. Cohen (AT&T Labs Research). 9:50 Nearly Tight Bounds on the Learnability of Evolution. Andris Ambainis, Richard Desper, Martin Farach (Rutgers University), and Sampath Kannan. Coffee Break: 10:10am -- 10:30am SESSION 8A: 10:30am -- 12:05pm CHAIR: Phil Klein 10:30 Improved Approximations for Shallow-Light Spanning Trees. Joseph (Seffi) Naor ( Technion University) and Baruch Schieber (IBM T.J. Watson Research Center). 10:55 Buy-at-Bulk Network Design Approximation Algorithms. Baruch Awerbuch (The Johns Hopkins University) and Yossi Azar. 11:20 A 2-Approximation Algorithm for the Directed Multiway Cut Problem. Joseph (Seffi) Naor (Technion University) and Leonid Zosin. 11:45 Nearly Linear Time Approximation Schemes for Euclidean TSP and other Geometric Problems. Sanjeev Arora (Princeton University). SESSION 8B: 10:30am -- 12:05pm CHAIR: Tao Jiang 10:30 Satisfiability Coding Lemma. Ramamohan Paturi (University of California, San Diego), Pavel Pudlak and Francis Zane. 10:55 The Minimization Problem for Boolean Formulas. Edith Hemaspaandra and Gerd Wechsung (Friedrich-Schiller-Universit\"at Jena). 11:20 Tight Bounds for Depth-Two Superconcentrators. Jaikumar Radhakrishnan (The Hebrew University of Jerusalem) and Amnon Ta-Shma. 11:45 Constant Depth Circuits and the Lutz Hypothesis. Jin-Yi Cai (University at Buffalo), Martin Strauss and D. Sivakumar (The University of Houston). End of Program: 12:05pm General Information Location All conference events will take place at the Ramada Resort Deauville on the island city of Miami Beach, Florida. Miami Beach is a 15 minute drive east of Miami International Airport and the city of Miami, and it a 45 minute drive south of Fort Lauderdale. Registration The registration desk will the open Sunday, October 19 >From 8 am to 10 pm and during the conference meeting times. Accomodations At the Ramada Resort Deauville, guests will enjoy everything that is Miami Beach. Bask in the sun or stroll endless stretches of golden beaches. Refresh your senses in the sparkling olympic sized swimming pool rimmed with a hundred dancing fountains. Relax those tired muscles in the rejuvenating Jacuzzi whirlpool spa. Enjoy the myriad of exciting attractions the area has to offer. Proudly displaying the coveted Gold Key Award for hospitality excellence, the Ramada Resort Deauville offers everything you would expect from a luxury resort and more. Each of the Ramada Resort Deauville's 550 spacious guest rooms and suites have been redecorated and refurbished. The decor is tropically casual with oversized beds, walk-in closets, color television and individual climate controlled air conditioning. All rooms have smoke detectors and sprinkler systems. Oceanfront rooms have private balconies. In addition to 700 feet of private beach, there are three all weather tennis courts, a well equipped exercise room, solarium and paddle boats on the beach. The concierge is pleased at all times to help with travel arrangements, golf starting times, sport fishing charters, as well as arranging trips to Jai Alai, thoroughbred tracks and greyhound racing. The Ramada Resort Deauville boasts two outstanding restaurants, each with its own specialty cuisine, plus a dinner buffet every evening in the lobby. Cafe De La Mer overlooking the pool, is a favorite for breakfast as well as lunch and dinner. For the super casual, come in your bathing suit to the Riviers Tap Grill. Meals are prepared from the freshest ingredients and served by a staff whose only desire is to please. Relax and enjoy the soft music in the Cyrano Lobby Bar. It's the perfect place to meet friends and unwind after a busy day of activities. OTHER SERVICES. For child care, the concierge can refer you to a bonded baby sitting service. Walgreens is open 24 hours across the street offering sundries, a full service pharmacy, and an ATM. Transportation Your most expeditious route is to fly into Miami International Airport (MIA). SuperShuttle service ((305) 871-2000) is available on the ground level (no reservation necessary) and can take you to the Ramada Resort Deauville on Miami Beach for $12. A taxi to the Ramada is about $30. An alternative is to fly into Fort Lauderdale International Airport (FLL). From there you can reach Miami Beach by car in about 45 minutes (see driving instructions below). DISCOUNT ON AMERICAN AIRLINES: In exchange for designation as the official airline of FOCS '97, American Airlines is offering the following discounts. If you are flying from the U.S. or Canada, you can receive an additional 5% discount off of all discount fares or a 10% discount off of all full fair tickets purchased 7 days in advance. To receive the group discount, you must call (800) 433-1790 to make your reservation and refer to star file A0807UC. DISCOUNT ON ALAMO RENTAL CAR: In exchange for designation as the official rental car agency of FOCS '97, Alamo Rental Car is offering a group discount. To obtain the discount, call (800) 732-3232 and refer to group ID number 526 569, Rate Code GR. DRIVING DIRECTIONS: If you rent a car at Miami International Airport, ask for directions to exit the airport onto State Road 112 heading east. Drive on to I-195 east which becomes Arthur Godfrey Drive (41st Street). Turn left on Collins. The Deauville will be on your right at 6701 Collins Avenue. >From Fort Lauderdale International Airport, ask your rental agent for directions to I-95 south. After about a 30 minute drive, exit on to I-195 east, and continue with the directions given for Miami Airport above. If you miss I-195, take 836 east and the MacArthur Causeway on to Miami Beach. Exit to 5th Street and drive east to Collins Avenue. Turn left to go north to Ramada. Parking at the Deauville is available for a fee of $5 per night. CLIMATE: The Average Daily Temperature for Miami for October is 72-83 F (22-28 C). Pack short-sleeved shirts, shorts, and of course, a swimming suit. Things to Do SOUTH BEACH is a short bus or taxi ride away down Collins Avenue. It is famed for its pedestrian mall, restaurants, and nightlife, and its restored vintage Art Deco hotels. VIZCAYA MUSEUM AND GARDENS. The 70-room house and gardens overlook Biscayne Bay on a 30-acre tract that includes a native hammock and more than 10 acres of formal gardens and fountains. In the house, 34 rooms of paintings, sculpture, antique furniture, and other decorative arts, are open to the public. 3251 S. Miami Ave., tel. 305/250-9133. Admission: $8 adults, $4 children 6-12. Guided 45-min tours available, group tours by appointment. House and ticket booth open daily 9:30-4:30; garden: daily 9:30-5:30. (Source: Fodors). LITTLE HAVANA. Hispanics and Anglos alike come to this area in downtown Miami to experience the flavor of traditional Cuban culture. EVERGLADES NATIONAL PARK. If you stay an extra day and have a car, consider visiting the Everglades. Alligators and nature's beauty await you. Conference Information PROCEEDINGS: Additional copies of the proceedings will be sold during the conference at the registration desk. There will also be a limited number of proceedings from FOCS '96 available at a discounted rate. There will be arrangements for shipping proceedings. ORGANIZING COMMITTEE CHAIR AND SITE COORDINATOR: Alok Aggarwal, IBM T.J. Watson Research Center. ORGANIZING COMMITTEE: Allan Borodin, Alok Aggarwal, Aditi Dhagat, Rene Peralta, Prabhakar Raghavan. PROGRAM COMMITTEE CHAIR AND TECHNICAL CHAIR: Anna Karlin, Department of Computer Science and Engineering, University of Washington, Box 352350, Seattle, WA 98195-2350. Email: focs-chair@cs.washington.edu. PROGRAM COMMITTEE: Kenneth L. Clarkson, Uriel Feige, Monika R. Henzinger, Tao Jiang, Ravi Kannan, Anna R. Karlin, Philip N. Klein, Hugo Krawczyk, Noam Nisan, Christos H. Papadimitriou, Steven Phillips, Greg Plaxton, Ronitt Rubinfeld, Raimund Seidel, Nir Shavit, and Madhu Sudan. LOCAL ARRANGEMENTS CHAIR AND TREASURER: Victor J. Milenkovic, Department of Mathematics and Computer Science, University of Miami, P.O. Box 248095, Coral Gables, FL 33124. Email: focs97@cs.miami.edu.