STOC '95 The 27th Annual ACM Symposium on Theory of Computing Las Vegas, Nevada May 29 - June 1, 1995 Sponsored by ACM SIGACT Registration for STOC '95 To qualify for the early registration fee, your registration applica- tion must be postmarked by Monday, May 1, 1995. Refund requests will be honored until May 8, 1995. The registration fee includes the Monday night reception, the Tuesday night business meeting, coffee breaks, lunches, and a copy of the proceedings. Send the form below, along with a check or money order in U.S. cur- rency made payable to STOC '95, to: STOC '95 Department of Computer Science University of Nevada Las Vegas NV 89154-4019 Name __________________________________________________________________________ Address _______________________________________________________________________ ___________________________________________________________________________ ___________________________________________________________________________ ___________________________________________________________________________ Email _________________________________________________________________________ Phone _________________________________________________________________________ FAX ___________________________________________________________________________ Affiliation (as you wish it to appear on your name tag): ___________________________________________________________________________ Please circle one amount below and fill in your membership num- ber if appropriate: #________________________________________________________. Registrants in the "Other" category will automatically become SIGACT members for a period of one year. Fee (US$) after May 1 ACM/SIGACT/IEEE or EATCS member 295 370 Student 125 175 Other 370 445 Check your dietary preference (lunches): Kosher 2 Vegetarian 2 No Restriction 2 Number of additional proceedings $60 each: Number of Banquet tickets (King Arthur's Tournament) $30 each (not included in registration fee): Check here if wheel chair seat needed at banquet: 2 Check here if Kosher meal needed at banquet: 2 (Vegetarian meals at banquet with no advance notice) Total included: $ Hotel Reservations Deadline: Friday, April 28, 1995 The conference will be held at the Tropicana Hotel, Las Vegas, NV. The rates for STOC '95 are posted below and apply from May 26 to June 4. Reservation requests received by the hotel after the April 28 dead- line are at your own risk: availability and rates are then no longer guaranteed. Refer to STOC '95 when making your reservations to obtain the rates listed. To make reservations by phone, call 702-739-2222 , 800-634-4000 or 800-GO-2-TROP , fax 702-739-2469. To make reservations, fill out the form below and fax it or mail it to the following address. Tropicana Hotel ATTN: STOC '95 registration Tropicana Avenue at Las Vegas Boulevard Las Vegas NV Credit card information or a deposit (in the form of a check or money order for one night's stay made payable to the Tropicana Hotel) must be included. Deposits will be refunded if the hotel is notified prior to 48 hours before arrival. Rate (Sunday-Thursday): $75 plus tax for a single or double room, $90 for a triple room. Weekend rates (Friday-Saturday): $95 plus tax for a single, double, or triple room. Check room type: Single 2 Double 2 Triple 2 Arrival date _______________________ Departure date _______________________ check-in time: 3:00 pm check-out time: 12:00 noon Name __________________________________________________________________________ Address _______________________________________________________________________ ___________________________________________________________________________ _____________________________________________________ Phone _______________ Sharing with ___________________________________________________________________ If paying by credit card please complete: American Express 2 Master Card 2 Visa 2 Carte Blanche 2 Diner's Club 2 Credit Card # ________________________________________________________________ Expiration date ______I authorize the Tropicana Hotel to charge the above account for the amount equal to one night's stay in case of a no-show. Signature _____________________________________________________________________ MONDAY, MAY 29, 1995 Reception: 7 pm - 10 pm TUESDAY, MAY 30, 1995 Continental Breakfast: 7:30 am - 8:30 am Session 1A: 8:30 am - 10:10 am Chair: Madhu Sudan 8:30 Improved Approximation Algorithms for Uniform Connec- tivity Problems: Samir Khuller, Univ. of Maryland ; Bal- aji Raghavachari, Univ. of Texas. 8:55 A Randomized Fully Polynomial Time Approximation Scheme for the All Terminal Network Reliability Problem: David R. Karger, MIT. 9:20 Adding Multiple Cost Constraints to Combinatorial Opti- mization Problems, with Applications to Multicommodity Flows: David Karger, MIT ; Serge Plotkin, Stanford. 9:45 Approximations for the Disjoint Paths Problem in High- Diameter Planar Networks: Jon Kleinberg, MIT ; E'va Tar- dos, Cornell. Session 1B: 8:30 am - 10:10 am Chair: Michael Ben Or 8:30 Secure Hypergraphs: Privacy from Partial Broadcast : Matthew Franklin, AT&T ; Moti Yung, IBM. 8:55 Incremental Cryptography and Application to Virus Pro- tection: Mihir Bellare, IBM ; Oded Goldreich, Shafi Gold- wasser, MIT & Weizmann. 9:20 Provably Secure Session Key Distribution_The Three Party Case: Mihir Bellare, IBM ; Phillip Rogaway, UC Davis. 9:45 Security of Quantum Protocols Against Coherent Measure- ments: Andrew Chi-Chih Yao, Princeton. Break: 10:10 am - 10:30 am Session 2A: 10:30 am - 11:20 am Chair: Andrei Broder 10:30 Efficient Stopping Rules for Markov Chains: L'aszl'o Lov'asz, Yale; Peter Winkler, AT&T. 10:55 A Computational View of Population Genetics: Yuval Ra- bani, Yuri Rabinovich, Univ. of Toronto; Alistair Sinclair, UC Berkeley. Session 2B: 10:30 am - 11:20 am Chair: Hal Gabow 10:30 Persistent Lists with Catenation via Recursive Slow-Down: Haim Kaplan, Robert E. Tarjan, Princeton. 10:55 On Data Structures and Asymmetric Communication Com- plexity : Peter Bro Miltersen, Univ. of Toronto; Noam Nisan, Hebrew Univ.; Shmuel Safra, Hebrew Univ. & Weizmann; Avi Wigderson, Hebrew Univ. ___________________________________________________________________________ ||||| | ||||| Invited session I: 11:30 am - 12:30 pm | ||||| | ||||| Chair: Richard Karp | ||||| | ||||| Percy Diaconis | ||||| | ||||| 11:30 What Do We Know About the Metropolis | ||||| Algorithm? : Persi Diaconis, Harvard ; Lau- | ||||| rent Saloff-Coste, Univ. Paul Sabatier. | ||||| | |||||______________________________________________________________________ | Lunch break: 12:30- 2:00 pm Session 3A: 2:00 pm - 3:15 pm Chair: Neil Immerman 2:00 A Lower Bound for Integer Multiplication with Read-Once Branching Programs: Stephen Ponzio, MIT. 2:25 Symmetric Logspace is Closed Under Complement : Noam Nisan, Amnon Ta-Shma, Hebrew Univ. 2:50 A Nearly Optimal Time-Space Lower Bound for Graph Con- nectivity Problem on the NNJAG Model : Jeff Edmonds, ICSI ; Chung Keung Poon, Univ. of Toronto. Session 3B: 2:00 pm - 3:15 pm Chair: Hal Gabow 2:00 Fast Protein Folding in the Hydrophobic-hydrophilic Model Within Three-eighths of Optimal : William E. Hart, Sorin Is- trail, Sandia Nat. Lab. 2:25 Large-Scale Assembly of DNA Strings and Space-Efficient Con- struction of Suffix Trees: S. Rao Kosaraju, Johns Hopkins; Arthur L. Delcher, Loyola College. 2:50 Transforming Cabbage into Turnip (polynomial algorithm for sorting signed permutations by reversals): Sridhar Han- nenhalli, Pavel Pevzner, Penn State Univ. Break: 3:15 pm - 3:45 pm Session 4A: 3:45 pm - 5:25 pm Chair: Michael Ben Or 3:45 How Many Queries are Needed to Learn? : Lisa Hellerstein, Northwestern Univ.; Krishnan Pillaipakkamnatt, Vijay Raghavan, Dawn Wilkins, Vanderbilt Univ. 4:10 Polynomial Bounds for VC Dimension of Sigmoidal Neural Networks: Marek Karpinski, Univ. Bonn; Angus Macintyre, Univ. Oxford. 4:35 Additive Versus Exponentiated Gradient Updates for Linear Prediction: Jyrki Kivinen, Univ. Helsinki ; Manfred K. War- muth, UC Santa Cruz. 5:00 On the Fourier Spectrum of Monotone Functions: Nader H. Bshouty, Christino Tamon, Univ. of Calgary. Session 4B: 3:45 pm - 5:25 pm Chair: Andrei Broder 3:45 Stochastic Contention Resolution With Short Delays: Prab- hakar Raghavan, IBM ; Eli Upfal, Weizmann & IBM. 4:10 Parallel Randomized Load Balancing : Micah Adler, Soumen Chakrabarti, Michael Mitzenmacher, Lars Rasmussen, UC Berkeley. 4:35 Bounding Delays in Packet-Routing Networks: Mor Harchol-Balter, David Wolfe, UC Berkeley. 5:00 Many-to-One Packet Routing on Grids: Yishay Mansour, Tel Aviv Univ.; Boaz Patt-Shamir, North- eastern Univ. Business Meeting: 8:00 pm - 10:00 pm WEDNESDAY, MAY 31, 1995 Continental Breakfast: 7:30 am - 8:30 am Session 5A: 8:30 am - 10:10 am Chair: Christos Papadimitriou 8:30 Improved Approximations of Packing and Covering Prob- lems: Aravind Srinivasan, Princeton & Rutgers. 8:55 Improved Approximation Guarantees for Minimum-Weight k-Trees and Prize-Collecting Salesmen: Baruch Awerbuch, Johns Hopkins & MIT ; Yossi Azar, Tel Aviv Univ.; Avrim Blum, Santosh Vempala, CMU. 9:20 Polynomial Time Approximation Schemes for Dense In- stances of N P -Hard Problems: Sanjeev Arora, Princeton; David Karger, MIT ; Marek Karpinski, Univ. Bonn. 9:45 A Constant-Factor Approximation for the k-MST Problem in the Plane: Avrim Blum, CMU ; Prasad Chalasani, Los Alamos Nat. Lab.; Santosh Vempala, CMU. Session 5B: 8:30 am - 10:10 am Chair: Moshe Vardi 8:30 The Relative Complexity of NPSearch Problems: Paul Beame, Univ. of Washington; Stephen Cook, Univ. of Toronto; Jeff Edmonds, ICSI ; Russell Impagliazzo, UC San Diego; Toniann Pitassi, Univ. of Pittsburgh. 8:55 Descriptive Complexity Theory over the Real Numbers: Erich Gr"adel, Klaus Meer, RWTH Aachen. 9:20 Average-Case Completeness of a Word Problem for Groups: Jie Wang, Univ. of N. Carolina. 9:45 On Real Turing Machines that Toss Coins: Felipe Cucker, Univ. Pompeu Fabra; Marek Karpinski, Univ. Bonn; Pascal Koiran, Ecole Normale Sup'erieure de Lyon; Thomas Lickteig, Kai Werther, Univ. Bonn.. Break: 10:10 am - 10:30 am Session 6A: 10:30 am - 11:20 am Chair: Christos Papadimitriou 10:30 Motion Planning for a Steering-Constrained Robot Through Moderate Obstacles: Pankaj K. Agarwal, Duke; Prab- hakar Raghavan, Hisao Tamaki, IBM. 10:55 Randomized Query Processing in Robot Path Planning : Ly- dia E. Kavraki, Jean-Claude Latombe, Rajeev Motwani, Stanford ; Prabhakar Raghavan, IBM. Session 6B: 10:30 am - 11:20 am Chair: Moshe Vardi 10:30 Distinguishing Tests for Nondeterministic and Probabilistic Machines: Rajeev Alur, AT&T ; Costas Courcoubetis, Univ. Crete; Mihalis Yannakakis, AT&T. 10:55 What's Decidable about Hybrid Automata?: Thomas A. Henzinger, Peter W. Kopke, Cornell ; Anuj Puri, Pravin Varaiya, UC Berkeley. __________________________________________________________________________ ||||| | ||||| Invited session II: 11:30 am - 12:30 pm | ||||| | ||||| Chair: Allan Borodin | ||||| | ||||| William Pulleyblank | ||||| | ||||| 11:30 Two Steiner Tree Packing Problems: | ||||| William Pulleyblank, IBM Research. | ||||| | |||||_____________________________________________________________________| Lunch break: 12:30 - 2:00 pm Session 7A: 2:00 pm - 3:15 pm Chair: Michael Ben Or 2:00 Linear-Time Encodable and Decodable Error-Correcting Codes: Daniel A. Spielman, MIT. 2:25 Subquadratic-Time Factoring of Polynomials over Finite Fields: Erich Kaltofen, Rensselaer Polytechnic Inst.; Vic- tor Shoup, Univ. Saarlandes. 2:50 Testing Multivariate Linear Functions: Overcoming the Generator Bottleneck : A. Funda Erg"un, Cornell . Session 7B: 2:00 pm - 3:15 pm Chair: Ketan Mulmuley 2:00 A Tight Lower Bound for Searching a Sorted Array : Arne Andersson, Lund Univ.; Johan Hastad, Royal Inst. of Tech., Stockholm; Ola Petersson, V"axj"o Univ. 2:25 Sorting in Linear Time? : Arne Andersson, Lund Univ.; Tor- ben Hagerup, Max Plank Inst.; Stefan Nilsson, Lund Univ.; Rajeev Raman, King's College London. 2:50 Lower Bounds for Sorting Networks: Nabil Kahale, Xerox PARC ; Tom Leighton, MIT ; Yuan Ma, Stanford ; C. Greg Plaxton, Univ. of Texas; Torsten Suel, NEC ; Endre Szemer'edi, Rutgers. Break: 3:15 pm - 3:45 pm Session 8A: 3:45 pm - 5:25 pm Chair: Madhu Sudan 3:45 A Parallel Repetition Theorem: Ran Raz, Weizmann. 4:10 Impossibility Results for Recycling Random Bits in Two- Prover Proof Systems: Uriel Feige, Weizmann; Joe Kilian, NEC. 4:35 Knowledge on the Average_Perfect, Statistical and Loga- rithmic: William Aiello, Bellcore; Mihir Bellare, IBM ; Ra- marathnam Venkatesan, Bellcore. 5:00 Explicit Dispersers with Polylog Degree: Michael Saks, Rut- gers; Aravind Srinivasan, Princeton; byShiyu ZhouRutgers. Session 8B: 3:45 pm - 5:25 pm Chair: Hal Gabow 3:45 Euclidean Spanners: Short, Thin, and Lanky : Sunil Arya, Max Planck Inst.; Gautam Das, Univ. of Memphis; David M. Mount, Univ. of Maryland ; Jeffrey S. Salowe, QuesTech, Inc.; Michiel Smid, Max Planck Inst. 4:10 Short Length Versions of Menger's Theorem: Zvi Galil, Columbia Univ. & Tel Aviv Univ.; Xiangdong Yu, Columbia Univ. 4:35 A 2-Level Cactus Model for the System of Minimum and Minimum+1 Edge-Cuts in a Graph and its Incremental Maintenance: Yefim Dinitz, Zeev Nutov, Technion. 5:00 Randomized Dynamic Graph Algorithms with Polylogarith- mic Time per Operation: Monika Rauch Henzinger, Cornell ; Valerie King, Univ. of Victoria. Dinner Show: 8:30 pm King Arthur's Tournament, at the Excalibur THURSDAY, JUNE 1, 1995 Continental Breakfast: 7:30 am - 8:30 am Session 9A: 8:30 am - 10:10 am Chair: Andrei Broder 8:30 Bubbles: Adaptive Routing Scheme for High-Speed Dy- namic Networks: Shlomi Dolev, Ben-Gurion Univ.; Evange- los Kranakis, Danny Krizanc, Carleton Univ.; David Peleg, Weizmann. 8:55 Wait-Free Made Fast : Yehuda Afek, Dalia Dauber, Dan Touitou, Tel Aviv Univ. 9:20 Tight Analyses of Two Local Load Balancing Algo- rithms: Bhaskar Ghosh, Yale; F. T. Leighton, MIT ; Bruce M. Maggs, CMU ; S. Muthukrishan, Rutgers; C. Greg Plaxton, R. Rajaraman, Univ. of Texas; Andr'ea W. Richa, CMU ; Robert E. Tarjan, Princeton & NEC ; David Zuckerman, Univ. of Texas. 9:45 Log-Space Polynomial End-to-End Communication: Eyal Kushilevitz, Technion; Rafail Ostrovsky, UC Berkeley & ICSI ; Adi Ros'en, Tel Aviv Univ. Session 9B: 8:30 am - 10:10 am Chair: Neil Immerman 8:30 Monotone Circuits for Connectivity Have Depth (log n)2-o(1): Mikael Goldmann, Johan Hastad, Royal Inst. of Tech. 8:55 Lower Bounds for Cutting Planes Proofs with Small Co- efficients: Maria Bonet, Univ. of Pennsylvania; Toni- ann Pitassi, Univ. of Pittsburgh; Ran Raz, Weizmann. 9:20 More on the Complexity of Negation-Limited Circuits: Robert Beals, Princeton & Rutgers; Tetsuro Nishino, Univ. Electro-Communications, Tokyo; Keisuke Tanaka, Japan Adv. Inst. of Science and Tech. 9:45 On Randomized One-Round Communication Complexity : Ilan Kremer, Noam Nissan, Dana Ron, Hebrew Univ. Break: 10:10 am - 10:30 am Session 10A: 10:30 am - 11:45 am Chair: Allan Borodin 10:30 Bounding the Power of Preemption in Randomized Schedul- ing : Ran Canetti, Weizmann; Sandy Irani, UC Irvine. 10:55 Bandwidth Allocation with Preemption: Amotz Bar-Noy, IBM ; Ran Canetti, Weizmann; Shay Kutten, IBM ; Yishay Mansour, Tel Aviv Univ.; Baruch Schieber, IBM. 11:20 Randomized and Multipointer Paging with Locality of Refer- ence: Amos Fiat, Tel Aviv Univ.; Anna R. Karlin, Univ. of Washington. Session 10B: 10:30 am - 11:45 am Chair: Christos Papadimitriou 10:30 Randomized Graph Products, Chromatic Numbers, and the Lovasz #-Function: Uriel Feige, Weizmann. 10:55 The k-Steiner Ratio in Graphs: Al Borchers, Ding-Zhu Du, Univ. of Minnesota. 11:20 Recognition of Graphs with Threshold Dimension Two: Thomas Raschle, Klaus Simon, ETH-Zentrum. Lunch break: 11:45 am - 1:45 pm Session 11A: 1:45 pm - 3:00 pm Chair: Ketan Mulmuley 1:45 Geometric Lower Bounds for Parametric Matroid Optimiza- tion: David Eppstein, UC Irvine. 2:10 Computing Faces in Segment and Simplex Arrangements: Nancy M. Amato, Texas A&M Univ.; Michael T. Goodrich, Johns Hopkins; Edgar A. Ramos, Univ. of Illinois. 2:35 A Delaunay Based Numerical Method for Three Dimensions: generation, formulation, and partition: Gary L. Miller, Dafna Talmor, CMU ; Shang-Hua Teng, Univ. of Minnesota; Noel Walkington, CMU. Session 11B: 1:45 pm - 3:00 pm Chair: Richard Karp 1:45 A Fully-Dynamic Data Structure for External Substring Search: Paolo Ferragina, Univ. Pisa; Roberto Grossi, Univ. Firenze. 2:10 String Matching in Lempel-Ziv Compressed Strings: Martin Farach, Rutgers; Mikkel Thorup, Univ. Copenhagen. 2:35 Work-Time-Optimal Parallel Algorithms for String Problems: Artur Czumaj, Univ. Paderborn; Zvi Galil, Columbia Univ. & Tel Aviv Univ.; Leszek Gasieniec, Warsaw Univ.; Kunsoo Park, Seoul Nat. Univ.; Wojciech Plandowski, Warsaw Univ. Break: 3:00 pm - 3:30 pm Session 12A: 3:30 pm - 4:20 pm Chair: Allan Borodin 3:30 On the Complexity of Bilinear Forms: Noam Nisan, Avi Wigderson, Hebrew Univ. 3:55 Lower Bounds for Off-Line Range Searching : Bernard Chazelle, Princeton. Session 12B: 3:30 pm - 4:20 pm Chair: Madhu Sudan 3:30 Optimal (up to Polylog Factors) Sequential and Parallel Algorithms for Approximating Complex Polynomial Zeros: Victor Y. Pan, CUNY. 3:55 Work Efficient Parallel Solution of Toeplitz Systems and Polynomial GCD : John H. Reif, Duke. End of Symposium: 4:20 pm Theory of Computer Science Working Group: 5:30 pm - 6:30 pm, Panel Discussion chaired by Richard Karp General Information Location: All conference events will take place at the Island Tower of the Tropicana Hotel on Tropicana Avenue, corner Las Vegas Boulevard (the Strip). Registration: The registration desk in the Foyer will be open from 6 - 8 pm on Monday, from 7:30 - 10:30 am Tuesday through Thursday, and from 3 - 5 pm Tuesday and Wednesday. Proceedings: Prepaid additional copies of the STOC '95 proceedings can be or- dered with the 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, while supplies last, for $60 per copy. Hotel Information: Our block of rooms at the Tropicana Hotel is being held from May 26 until June 4. We encourage you to make your reserva- tions by telephone. The Tropicana Hotel is located at the fabulous Four Corners. This newest area of the world-famous Las Vegas Strip has entertain- ment for the whole family. Four skywalks equipped with escalators and elevators carry pedestrian traffic safely across the major thor- oughfares of Las Vegas Boulevard and Tropicana Avenue, linking the Tropicana Hotel and Casino with the mighty MGM Grand to the north and the medieval-themed Excalibur and the Egyptian- themed Luxor to the west. Four Corners is a 24-hour entertain- ment city in itself, with restaurants, shows, and, of course, plenty of gaming action. The area between the Island Tower and the main Paradise Tower is beautifully landscaped with tropical vegetation and waterfalls, and features swim-up blackjack. Banquet: In lieu of the usual banquet, STOC '95 will arrange for participants to attend the fabulous King Arthur's Tournament, a medieval-style dinner show featuring knights jousting (with real horses), magic, and treachery. Serving wenches and lackeys will bring your me- dieval style dinner, which you eat with your fingers. Cheer for your knight. If he gets beaten, it's a shame. The show is "family," in case you wish to bring the children. Showtime is 8:30. From the front entrance of the Tropicana (near the Easter Island Heads) cross Las Vegas Boulevard on the pedes- trian skywalk. Enter the fabulous Excalibur through the main portuculis, descend the Fountain Staircase to Fantasy Faire, then look for King Arthur's Arena. Or, arrive early, and watch the Dragon, who appears every hour on the hour, starting at 6:00 P.M., in the moat, only to be driven back by Merlin's magic. Or take the escalator in the middle of the casino floor up to the Medieval Village, and spend some time in the shops or watch the free shows, scheduled every 30 minutes on the Jester Stage. Those who order advance tickets with their registration will be seated in a preferred section along with other STOC participants. There is no way to ask for a specific section if tickets are purchased individually. Please check the appropriate box on the registration form. Children under the age of 4 are free, but must sit on an adult's lap and will not be served an extra meal. Kosher meals are available with advance notice (check box). Vegetarian meals are available with no advance notice. Official Airlines: American Airlines has been appointed the official air carrier for STOC '95. When calling for reservations, be sure to mention the Star File number NBR - S0455MA, and refer to our event as "STOC." Telephone 800-433-1790. Getting to Las Vegas and the Hotel: Las Vegas is served by McCarran Airport, only 2 miles from the Tropicana Hotel. Taxi Fare is approximately $8. The Gray Line Shuttle costs $3.75. If you plan to travel anywhere in the Las Vegas area other than along the Strip, it is advisable to have a car. Rentals are readily available. Child Care: Hotel room child care is available 24 hours through Vegas Valley Babysitting at 871-5161. The minimum charge is $34 for 2 children for 4 hours. Call to get other rates. Arrange at least 8 hours in advance. Climate: The day-time temperature in Las Vegas at the end of May varies be- tween 70 and 90 degrees Fahrenheit. Night-time temperatures can be 30 degrees lower. The humidity is very low, and rain is unlikely. Things to Do: Four Corners is the Southernmost and newest focal point of the famed Las Vegas "Strip." with over 15,000 hotel rooms at the inter- section of Las Vegas and Tropicana Boulevards. On the Southeast corner sits the long-established Tropicana. The new Island Tower, site of STOC '95, can be reached from the main Paradise Tower by the 200-meter Island Walk, with moving slidewalks, overlooking the tropically landscaped pool and garden area. The Southwest corner holds the Excalibur (medieval theme) with 4000 rooms, formerly the largest hotel in the world, but recently eclipsed by the mighty MGM Grand. Just south of the Excalibur is the newly opened Luxor, shaped like a pyramid 36 stories high, and topped with a fixed searchlight that stabs directly upward, and guarded by a better-than-the-real-one Sphinx (this one has a nose). Inside, you can ride a Nile riverboat all around the circumference. From the activity level, one floor above the Casino, you can descend into the Lost City, 8000 feet beneath the surface, discovered while digging the foundations of the Luxor. On the Northeast corner is the Lion entrance to the MGM Grand, with over 5000 rooms. Behind the Lion's head entrance is the Emerald City, where for only $5.95 you can walk the Yellow Brick Road. Talking mannequins are everywhere, including the Wizard, the Wicked Witch of the West, and a bar mannequin that tells jokes around the clock. Beyond the food court, which features Chinese, Milanese, Western, English, etc., etc., cuisine (not to mention MacDonalds and several other fast food outlets), you find the Theme Park, where you can ride all day for $15 if you're at least 42 inches tall. (Individual rides are $3.50.) South of the Luxor is the now dwarfed Hacienda (Spanish-American theme), and East of the Trop is the San Remo. New York, New York is under construction in the Northwest Corner of Four Corners. A scant mile (15 minutes brisk walk) North of Four Corners is Cae- sar's Palace, with the fabulous Forum Shops, Planet Hollywood, upscale shopping, and Roman gods that talk and move every hour. Just beyond lies the Mirage, featuring a dolphin habitat, a white tiger habitat, a rain forest (indoors) and a volcano that erupts every 15 minutes during the evening. Just North of the Mirage is Trea- sure Island, whose lagoon features a battle to the death between two ships every 90 minutes. (The pirates always win.) Treasure Island is home to Myst'ere, rated one of the top 10 stage shows of 1994 by TIME Magazine. Call 702-894-7722 for tickets. All of this new entertainment is part of a quite deliberate transformation of Las Vegas from a mere gambling capital to a vacation spot with something to offer for the entire family. Late May has ideal weather for outdoor activities. There is Hoover Dam, Lake Mead, Red Rock Canyon State Park. Outdoor enthusi- asts can go hiking on the many trails on Mt. Charleston, or take a rafting trip (choose white-water or calm) down the Colorado River. Scenic Airlines, 739-1900, walking distance from the Tropicana, has Grand Canyon overflights for as little as $99.50. For the children, there is the Lied Discovery Children's Museum, 382-5437 , or the Las Vegas Natural History Museum 384-3466 . More information can be obtained from the STOC '95 World Wide Web page, URL http://hercule.csci.unt.edu/stoc95. Program Committee: Hagit Attiya, Michael Ben Or, Allan Borodin (Chair), Andrei Broder, Hal Gabow, Neil Immerman, Richard Karp, Leonid Levin, Ketan Mulmuley, Christos Papadimitriou, Rob Schapire, Claus Schnorr, Madhu Sudan, Moshe Vardi, Frances Yao. Local Committee: Lawrence Larmore (General Chair), Wolfgang W. Bein (Treasurer), Ajoy Datta, Laxmi Gewali (Registration Co-Chairs). Publicity: Ian Parberry. Site Coordinator: Alok Aggarwal.