------------------------------------------------------------------------ STOC '92 Advance Program Victoria, British Columbia, Canada May 4-6, 1992 The 24th Annual ACM Symposium on Theory of Computing is sponsored by the ACM Special Interest Group for Automata and Computability (SIGACT). STOC '92 ADVANCE REGISTRATION FORM Please fill in the form below and send it, along with a check or money order in U.S. or Canadian currency made payable to "STOC '92," to: Prof. John Ellis, STOC '92 Treasurer, Department of Computer Science University of Victoria, Victoria, B.C., Canada V8W 3P6 The regular registration fee includes the Sunday night reception, the Monday night business meeting, the Tuesday night banquet, three lunches, the coffee breaks, and the proceedings. Student registration includes all of the above except the banquet. Nonmember registration includes all of the above and also membership in SIGACT for the following year. Circle the relevant items below. Refund requests will be honored until April 10, 1992. To qualify for the early fee, advance registration materials must be received by April 10. Early Fee Late Fee (after April 10) ACM or SIGACT members $US 280 ($Can 330) $US 340 ($Can 400) Non-ACM, non-SIGACT members $US 340 ($Can 400) $US 390 ($Can 459) Full-time Students $US 70 ($Can 82) $US 120 ($Can 141) Extra banquet ticket(s) $US 40 ($Can 47) Extra proceedings (ea.) $US 45 ($Can 53) Outings: Butchart Gardens by Double Decker $US 22 ($Can 26) (Sun. / Mon. / Wed.) for Children 5-11 $US 8 ($Can 9) Sea Kayaking (all day trip) $US 80 ($Can 94) (Sun. / Thurs.) Island Excursion by Zodiak $US 28 ($Can 33) (Mon. / Wed.) Theory Group Bungee Jumping $US 105 ($Can 124) (Sun. all day) Survivors Dinner Cruise $US 42 ($Can 49) (Wed.) See the General Information section for details concerning the outings. Please note: Outings are not sponsored by the Association for Computing Machinery or the ACM Special Interest Group on Automata and Computability Theory and should not be considered part of the conference. In addition, attendees wishing to participate in these activites will be required to sign a waiver and release form prior to participation in the outings. Availability may be limited; first come first served. Prepayment required. Name _________________________________________________________________ ACM Membership Number (required for member discount) _________________ Affiliation __________________________________________________________ Address ______________________________________________________________ City ______________ State/Country ____________Postal Code ____________ Daytime Phone _________________ Email address ________________________ Dietary restriction:____________Special requests:_____________________ HOTEL INFORMATION Room blocks are being held at the world-famous Empress Hotel on Victoria's Inner Harbor, adjacent to the Victoria Conference Centre, from Saturday May 3 through Wednesday May 7. To make reservations by phone, call one of the following numbers and be sure to mention STOC '92: \\ from the U.S.A. 800-828-7447 from Canada 800-268-9420 or 800-268-9411 elsewhere 604-384-8111 reservation fax 604-381-4334 The room rate is $Can 115 per night (approximately $US 97) for either a single or a double room. (A 7% general service tax on accomodations is refundable to non-Canadian residents. Information concerning the GST refund procedure will be available in the registration packet.) The room block is being held through APRIL 5 and reservations should be made before this date. STOC '92 PROGRAM All events will be held in the Victoria Conference Centre adjacent to the Empress Hotel. The welcoming reception will be held in Salon A (upstairs) at the Conference Centre. The registration desk on the main floor of the Conference Centre will be open 6-9 pm Saturday, noon-11 pm Sunday and 8 am - 5 pm Monday through Wednesday. SUNDAY, May 3, 1992 Reception: 8 pm - 11 pm, Conference Centre Salon A MONDAY, May 4, 1992 Session 1A: 8:45 am - 10:20 am, Lecture Theatre Chair: M. Naor 8:45 Biased Random Walks Y. Azar, A.Z. Broder, A.R. Karlin, N. Linial, S. Phillips 9:10 Approximations of General Independent Distributions G. Even, O. Goldreich, M. Luby, N. Nisan, B. Velickovic 9:35 Sample Spaces Uniform on Neighborhoods L.J. Schulman 10:00 Balanced Matroids T. Feder, M. Mihail Session 1B: 8:45 am - 10:20 am, Salon C Chair: E. Tardos 8:45 Competitive Algorithms for Distributed Data Management Y. Bartal, A. Fiat, Y. Rabani 9:10 New Algorithms for an Ancient Scheduling Problem Y. Bartal, A. Fiat, H. Karloff, R. Vohra 9:35 Alphabet Independent Two Dimensional Matching A. Amir, G. Benson, M. Farach 10:00 Hunting Lions in the Desert Optimally, or A Constant-Time Optimal Parallel String-Matching Algorithm Z. Galil Break 10:20 am - 11:00 am Plenary Session 11:00 am - 12:00 noon, Lecture Theatre Chair: N. Pippenger 11:00 Networks and Algorithms for Message Routing in Parallel Machines F.T. Leighton Lunch break: 12:00 - 1:30 pm Session 2A: 1:30 pm - 3:05 pm, Lecture Theatre Chair: A. Borodin 1:30 Computing Frobenius Maps and Factoring Polynomials J. von zur Gathen, V. Shoup 1:55 Parallel Computation Over Hyperbolic Groups J-Y. Cai 2:20 Structure Forest and Composition Factors for Small Base Groups in Nearly Linear Time R. Beals, A. Seress 2:45 Feasibility Testing for Systems of Real Quadratic Equations A.I. Barvinok Session 2B: 1:30 pm - 3:05 pm, Salon C Chair: N. Pippenger 1:30 Fault Tolerant Planar Communication Networks G. Lin 1:55 Existence and Construction of Edge Disjoint Paths on Expander Graphs A.Z. Broder, A.M. Frieze, E. Upfal 2:20 Simple Algorithms for Routing on Butterfly Networks with Bounded Queues B.M. Maggs, R. Sitaraman 2:45 Computing with Faulty Arrays Y. Aumann, M. Ben-Or Break 3:05 pm - 3:30 pm Session 3A: 3:30 pm - 5:05 pm, Lecture Theatre Chair: A. Wigderson 3:30 Linear Decision Trees: Volume Estimates and Topological Bounds A. Bjorner, L. Lovasz, A. Yao 3:55 Entropy and Sorting J. Kahn, J.H. Kim 4:20 Randomized versus Nondeterministic Communication Complexity P. Beame, J. Lawry 4:45 Exponential Lower Bounds for the Pigeonhole Principle P. Beame, R. Impagliazzo, J. Krajicek, T. Pitassi, P. Pudlak, A. Woods Session 3B: 3:30 pm - 5:05 pm, Salon C Chair: E. Tardos 3:30 Finding Approximate Separators and Computing Tree Width Quickly B.A. Reed 3:55 Finding Small Edge Cuts in Planar Graphs S.B. Rao 4:20 The Complexity of Multiway Cuts E. Dahlhaus, D.S. Johnson, C.H. Papadimitriou, P. Seymour, M. Yannakakis 4:45 Graph Decomposition is NPC -- A Complete Proof of Holyer's Conjecture D. Dor, M. Tarsi Business Meeting: 9:00 pm - 11:00 pm, Lecture Theater TUESDAY, May 5, 1992 Session 4A: 8:45 am - 10:20 am, Lecture Theatre Chair: R. Ladner 8:45 Online Minimization of Transition Systems D. Lee, M. Yannakakis 9:10 Exponential Determinization for omega-Automata with a Strong Fairness Acceptance Condition S. Safra 9:35 A New Recursion-Theoretic Characterization of the Polytime Functions S. Bellantoni, S. Cook 10:00 Asymptotic Conditional Probabilities A. Grove, J.Y. Halpern, D.Koller Session 4B: 8:45 am - 10:20 am, Salon C Chair: B. Chazelle 8:45 Efficient Program Transformations for Resilient Parallel Computation via Randomization Z.M. Kedem, K.V. Palem, M.O. Rabin, A. Raghunathan 9:10 Efficient PRAM Simulation on a Distributed Memory Machine R.M. Karp, M. Luby, F. Meyer auf der Heide 9:35 A Deterministic Poly(log log N)-Time N-Processor Algorithm for Linear Programming in Fixed Dimension M. Ajtai, N. Megiddo 10:00 On Computing a Maximal Independent Set in a Hypergraph of Constant Dimension in Parallel P. Kelsen Break 10:20 am - 11:00 am Plenary Session 11:00 am - 12:00 noon, Lecture Theatre Chair: R. Ladner Computational Learning Theory D. Angluin Lunch break: 12:00 - 1:30 pm Session 5A: 1:30 pm - 3:05 pm, Lecture Theatre Chair: D. Joseph 1:30 Learning Arithmetic Read-Once Formulas N.H. Bashouty, T.R. Hancock, L. Hellerstein 1:55 Fast Learning of k-Term DNF Formulas with Queries A. Blum, S. Rudich 2:20 Can Finite Samples Detect Singularities of Real-Valued Functions? S. Ben-David 2:45 A Logspace Algorithm for Tree Canonization S. Lindell Session 5B: 1:30 pm - 3:05 pm, Salon C Chair: M. Naor 1:30 A Hypercubic Sorting Network with Nearly Logarithmic Depth C.G. Plaxton 1:55 Small-Depth Counting Networks M. Klugerman, C.G. Plaxton 2:20 Shallow Multiplication Circuits and Wise Financial Investments M.S. Paterson, U. Zwick 2:45 Symmetry and Complexity L. Babai, R. Beals, P. Takacsi-Nagy Break: 3:05 pm - 3:30 pm Session 6A: 3:30 pm - 5:05 pm, Lecture Theatre Chair: A. Wigderson 3:30 When do Extra Majority Gates Help? Polylog(n) Majority Gates are Equivalent to One R. Beigel 3:55 Representing Boolean Functions as Polynomials Modulo Composite Numbers D.A. Mix Barrington, R. Beigel, S. Rudich 4:20 On the Degree of Boolean Functions as Real Polynomials N. Nisan, M. Szegedy 4:45 On the Degree of Polynomials that Approximate Symmetric Boolean Functions R. Paturi Session 6B: 3:30 pm - 5:05 pm, Salon C Chair: N. Alon 3:30 A Subexponential Randomized Simplex Algorithm G. Kalai 3:55 Polynomial Algorithms for Linear Programming over the Algebraic Numbers I. Adler, P.A. Beling 4:20 Fully Dynamic Planarity Testing Z. Galil, G.F. Italiano, N. Sarnak 4:45 Planar Separators and Parallel Polygon Triangulation M.T. Goodrich Banquet and STOC Follies: 7 pm - midnight, Salon A WEDNESDAY May 6, 1992 Session 7A: 8:45 am - 10:20 am, Lecture Theatre Chair: B. Chazelle 8:45 Ray Shooting and Parametric Search P.D. Agarwal, J. Matousek 9:10 On the Angular Resolution of Planar Graphs S.M. Malitz, A. Papakostas 9:35 Ham-Sandwich Cuts in d-Dimensional Euclidean Space C-Y. Lo, J. Matousek, W. Steiger 10:00 A Decomposition of Multi-dimensional Point-sets with Applications to k-Nearest-Neighbors and n-Body Potential Fields P.B. Callahan, S.R. Kosaraju Session 7B: 8:45 am - 10:20 am, Salon C Chair: M. Herlihy 8:45 Adapting to Asynchronous Dynamic Networks with Polylogarithmic Overhead B. Awerbuch, B. Patt-Shamir, D. Peleg, M. Saks 9:10 Competitive Distributed Job Scheduling B. Awerbuch, S. Kutten, D. Peleg 9:35 Improved Distributed Algorithms for Coloring and Network Decomposition Problems A. Panconesi, A. Srinivasan 10:00 Efficient Fault Tolerant Algorithms for Resource Allocation in Distributed Systems M. Choy, A.K. Singh Break: 10:20 am - 11:00 am Plenary Session: 11:00 am - 12:00 noon, Lecture Theatre Chair: R. Ladner 11:00 The History and Status of the P versus NP Problem M. Sipser Lunch break: 12:00 - 1:30 pm Session 8A: 1:30 pm - 3:05 pm, Lecture Theatre Chair: N. Pippenger 1:30 RL is Contained in SC N. Nisan 1:55 On the Complexity of String Operations J. Simon, M. Szegedy 2:20 Average Case Intractability of Diophantine and Matrix Problems R. Venkatesan, S. Rajagopalan 2:45 On the Hardness of Computing the Permanent of Random Matrices U. Feige, C. Lund Session 8B: 1:30 pm - 3:05 pm, Salon C Chair: M. Herlihy 1:30 Simple and Efficient Bounded Concurrent Timestamping C. Dwork, O. Waarts 1:55 Self-Stabilizing Symmetry Breaking in Constant-Space A. Mayer, Y. Offek, R. Ostrovsky, M. Yung 2:20 A Correctness Condition for High Performance Multiprocessors H. Attiya, R. Friedman 2:45 Target Shooting with Programmed Random Variables G. Brightwell, T.J. Ott, P. Winkler Break: 3:05 pm - 3:30 pm Session 9A: 3:30 pm - 5:05 pm, Lecture Theatre Chair: M. Naor 1:30 Communication Complexity of Secure Computation M. Franklin, M. Yung 1:55 Making Zero-Knowledge Provers Efficient M. Bellare, E. Petrank 2:20 A Note on Efficient Zero-Knowledge Proofs and Arguments J. Kilian 2:45 Two-Prover One-Round Proof Systems: Their Power and Their Problems U. Feige, L. Lovasz Session 9B: 3:30 pm - 5:05 pm, Salon C Chair: D. Joseph 1:30 On the All-Pairs-Shortest-Path Problem R. Seidel 1:55 A Parallel Randomized Approximation Scheme for Shortest Paths P.N. Klein, S. Sairam 2:20 Biconnectivity Approximations and Graph Carvings S. Khuller, U. Vishkin 2:45 Epsilon-Approximations with Minimum Packing Constraint Violation J-H. Lin, J.S. Vitter GENERAL INFORMATION Conference Registration and Events The regular registration fee includes the Sunday night reception, the Monday night business meeting, the Tuesday night banquet, three lunches, the coffee breaks, and the proceedings. Student registration includes all of the above except the banquet. The registration desk will be open 6-9 pm Saturday, noon-11 pm Sunday and 8 am - 5 pm Monday through Wednesday. Informal Communication of Recent Results Several things will be done to facilitate the informal communication of recent research by conference participants. Abstracts of up to one page in length per paper are invited; these will be compiled and made available at the conference. Please bring a few copies of the full paper, if it is available, so that interested parties can obtain it from you at the meeting. Abstracts should be sent by April 15 to Mike Fellows, STOC '92 Conference Chair (preferably as a latex file by email to: [log in to unmask] ). Volunteers who wish to organize informal problem sessions or other informal presentations are encouraged to contact the Conference Chair. These sessions will be publicized in electronic updates concerning the conference, and there will be notice board at the meeting to facilitate informal exchanges. STOC Follies Following the banquet, we will enjoy the first-ever STOC Follies. Remember that strange character who was once your thesis advisor? The theme for the follies is, ``Revenge of the Students.'' Now's your chance to spoof that personality that once loomed large in your intellectual life! No statute of limitations! Outings A number of outings have been planned, all of which require prepayment, and any of which may be cancelled (with refund, of course) if there is insufficient interest. The double-decker bus trips to Butchart Gardens are available on Sunday afternoon (2 pm) and on Monday and Wednesday afternoon (departure time TBA, around 5 pm probably). The buses are reserved for conference participants and their families. The price of $22 (U.S.) includes the scenic bus ride and admission to the gardens. Children who appear to be under 11 can squeak by for $8 (U.S.), and toddlers for free. On Sunday (and Thursday, if there is sufficient interest) an all day sea-kayaking excursion is available for a limited number of participants. Included in the price of $80 (U.S.) is transportation, equipment, instruction (no experience necessary), and a gourmet lunch on one of the nearby wild islands (you understand how you will get there!). Those who prefer less personal effort can make a two hour afternoon trip to the islands by zodiak on Monday or Wednesday (after the sessions, or nearly so) for $28 (U.S.). The bungee jumping, supervised by bungee scientists, is from a bridge over a river gorge in a spectacular setting. The location is about 2 hours north of Victoria, quite a scenic drive. The price of $105 (U.S.) includes transportation, training (such as it is) and equipment. On Saturday, local arrangements is planning a surfing expedition to Sombrio, about 2 hours west (also a pretty drive!) from Victoria. Inquire if you are interested. For the survivors, there will be an evening dinner cruise on Wednesday (opportunity limited by the size of the vessel). $45 (U.S.) pays for everything, including Canadian wine. Depending on interest, other outings may be planned; inquire. Proceedings Additional copies of the STOC '92 proceedings can be ordered with the advance registration form and will be available for pick-up at registration. There will also be copies available at the registration desk on a first come, first served basis for $45 (U.S.) per copy. Hotel Information The conference will be held at the beautiful and historic Empress Hotel and the adjacent Victoria Conference Centre. Our room rate at the Empress is priced at approximately two-thirds of the usual rate charged at this time of year at this famous tourist and honeymoon destination. The address of the Empress is 721 Government Street, Victoria, British Columbia, Canada V8W 1W5. The phone number in Victoria is (604) 384-8111. Our block of rooms is being held from Saturday, May 2, until Wednesday, May 6. To insure availability at the conference rate, reservations should be made before April 5. Child Care The Empress provides in-house babysitting (for a price) both days and evenings. During conference hours there will also be available, through conference local arangements, childcare including crafts, games, mathematics and outings for a nominal fee, and arrangement in advance. Student Accomodations For graduate students and others on a shoe-string budget, a small block of student apartments is being held at the University of Victoria. Reservations for these should also be made before April 5, by phoning (604) 721-8396. For a shared room, the rate comes to about $18 (U.S.) per night per person, including breakfast and all taxes. Extended stays are possible, which may be useful if you are attaching a vacation to the conference. UVic is located a few miles from downtown. The campus will be relatively quiet, as the Spring term ends in mid-April. Bus transportation between downtown and campus is frequent and convenient. Airline Information United Airlines and Canadian Airlines are the official air carriers for STOC '92. In contacting Canadian Airlines, you or your travel agent should mention the STOC '92 Convention Registration Number: 0306. In contacting United Airlines, you or your travel agent should mention our meeting code number: 525 XC. From the U.S. and Canada, United's convention reservation number is (800) 521-4041. The discount offered by Canadian Airlines is essentially 15% off economy or excursion fares, subject to various conditions. The discount offered by United Airlines is 5% off restricted coach fares, and a discount of up to 45% off unrestricted coach fares, depending on where your travel originates. Discounts on rental cars from Hertz are also available through the United Airlines convention desk at the number above. Getting to Victoria There are two principal ways to get to Victoria, located at the southern tip of Vancouver Island --- by connecting through Vancouver, or through Seattle, to Victoria's International Airport. From the airport, there are shuttle buses to downtown Victoria (30 km) costing about $15. The price of a taxi should be about $30 Canadian. There are also a number of appealing alternative ways of getting to Victoria. The float planes of Lake Union Air fly between Lake Union in Seattle and the harbour right in front of the Empress. This costs little or no more than the usual airline connection between Seattle and Victoria and is quite a thrill. A scenic passenger ferry, the Clipper, runs between Seattle and Victoria and is relatively inexpensive. There is a car ferry from Port Angeles on the Olympic penninsula to downtown Victoria. For this route, timing would be important since the Port Angeles ferry does not run frequently. The scenic B.C. ferry threads its way through the Gulf Islands from Tsawassen, near Vancouver, to Schwarz Bay, about 35 km from Victoria. The B.C. ferry runs hourly, so one reasonable possibility is to rent a car in Vancouver and drive to Victoria, crossing on the ferry from Tsawassen, a beautiful 2 hour trip. It is also possible to take a bus from Vancouver International Airport to Victoria, crossing on this same ferry. Helijet Airways flies between Vancouver International Airport and downtown Victoria. Things to Do Victoria is picturesque, historic city with considerable character. It has a real fisherman's wharf within walking distance of the Empress, a small but vibrant Chinatown, and several venues for English high tea. Victoria is justly famous for its gardens; a nice one adjoins the Empress and the Conference Centre. Vancouver Island is rugged and beautiful, as is B.C. in general. There is an excellent park system in British Columbia, surely one of the best in the world. For those attracted to the wilderness, the conference could be part of an excellent family vacation expedition. Tourism Victoria (604) 382-2127 will happily send maps and information about Victoria, Vancouver Island and British Columbia. Climate Early May weather in Victoria is ``variable,'' with some sunshine likely, but with a possibility of some cool weather and rain. Daily temperatures typically range from 7-17 degrees C in this season. Further Information Updates and further information can be obtained automatically by sending an email message to [log in to unmask] Or you can contact the conference and local arrangements chair Mike Fellows Department of Computer Science University of Victoria Victoria, B.C. V8W 3P6 Canada (604) 721-7299, [log in to unmask]