COLT '91 Workshop on Computational Learning Theory Monday, August 5 through Wednesday, August 7, 1991 University of California, Santa Cruz, California The workshop will be held on campus, which is hidden away in the redwoods on the Pacific coast of Northern California. We encourage you to come early so that you will have time to enjoy the area. You can arrive on campus as early as Saturday, August 3. You may want to learn wind surfing on Monterey Bay, go hiking in the redwoods at Big Basin Redwoods State Park, see the elephant seals at Ano Nuevo State Park, visit the Monterey Bay Aquarium, or see a play at the Santa Cruz Shakespeare Festival on campus. The workshop is being held in-cooperation with ACM SICACT and SIGART, and with financial support from the Office of Naval Research. 1. Flight tickets: San Jose Airport is the closest, about a 45 minute drive. San Francisco Airport is about an hour and forty-five minutes away, but has slightly better flight connections. The International Travel Bureau (ITB -- ask for Peter) at (800) 525-5233 is the COLT travel agency and has discounts for some non-Saturday flights. 2. Transportation from the airport to Santa Cruz: The first option is to rent a car and drive south from San Jose on 880/17. When you get to Santa Cruz, take Route 1 (Mission St.) north. Turn right on Bay Street and follow the signs to UCSC. Commuters must purchase parking permits for 2.50/day from the parking office or the conference satellite office. Those staying on campus can pick up permits with their room keys. Various van services also connect Santa Cruz with the the San Francisco and San Jose airports. The Santa Cruz Airporter (408) 423-1214 (or (800)-223-4142 from the airport) has regularly scheduled trips (every two hours from 9am until 11pm from San Jose); Over The Hill Transportation (408) 426-4598 and ABC Transportation (408) 662-8177 travel on demand and should drop you off at the dorms. Call these services directly for reservations and prices. Peerless Stages (phone: (408) 423-1800) operates a regularly scheduled bus between the San Jose Airport and Downtown costing 4.30 and taking about an hour and a quarter. The number 1 bus serves the campus from the Santa Cruz metro center, ask the driver for the Crown-Merrill apartments. 3. Conference and room registration: Please fill out the enclosed form and and send it to us with your payment. It must be postmarked by June 24 and received by July 1 to obtain the early registration rate and guarantee the room. Conference attendance is limited by the available space, and late registrations may need to be returned. Your arrival : Enter the campus at the main entrance following Bay Street. Follow the main road, Coolidge Drive, up into the woods and continue until the second stop sign. Turn right and go up the hill. If you need a map, send E-mail to Jean (jean@cs.ucsc.edu). This road leads into the Crown/Merrill apartments. The whole route will be marked with signs. When you get to the campus, follow the All Conferences signs. As you enter the redwoods the signs will specify particular conferences, such as the International Dowsing Competition and COLT '91. The COLT '91 signs will lead you to the Crown/Merrill apartments. In the center of the apartment complex you will find the Crown/Merrill satellite office of the Conference Office. They will have your keys, meal cards, parking permits, and lots of information about what to do in Santa Cruz, If you get lost or have questions about your room: Call the Crown/Merrill satellite office at (408) 459-2611 . Someone will be at that number all the time, including Saturday and Sunday night. THE FUN PART The weather in August is mostly sunny with occasional summer fog. Bring T-shirts, slacks, shorts, and a sweater or light jacket, as it cools down at night. For information on the local bus routes and schedules, call the Metro center at (408) 425-8600. You can rent windsurfers and wet suits at Cowell Beach . Sherryl (home (408) 429-5730, message machine (408) 429-6033) should be able to arrange lessons and/or board rentals. The main road that leads into the campus is Bay Street. If you go in the opposite direction, away from campus, you will run into a T-intersection at the ocean at the end of Bay Street. Turn left and stay to the right. The road will lead you down to the Boardwalk. Cowell Beach is at the base of the Dream Inn on your right. If you turn right instead of left at the T-intersection at the bottom of Bay Street, you will be driving along Westcliff Drive overlooking the ocean. The road passes by the lighthouse (where you can watch seals and local surfing pros) and dead-ends at Natural Bridges State Park. Westcliff Drive also offers a wonderful paved walkway/bikeway, about 2 miles long. Big Basin Redwoods State Park is about a 45 minute drive from Santa Cruz and there are buses that leave from the downtown Metro Center. You can hike for hours and hours among giant redwoods on the 80 miles of trails. We recommend Berry Creek Falls (about 6 hours for good hikers), but even a half hour hike is worth it! Some of the tallest coastal redwoods on this planet can be found here: the Mother of the Forest is 101 meters (329 feet) high and is on the short (0.06 mile) Redwood trail. For park information call (408) 338-6132. This is your chance to see some Northern Elephant seals, the largest of the pinnipeds. Ano Nuevo State Park is one of the few places in the world where these seals go on land for breeding and molting (August is molting season). Ano Nuevo is located about 20 miles north of Santa Cruz on the coast (right up Highway 1). The park is open from 8am until sunset, but you should plan on arriving before 3pm to see the Elephant seals. Call Ano Nuevo State Park at (415)879-0595 for more information. At the Monterey Bay Aquarium , you can see Great White sharks, Leopard sharks, sea otters, rays, mollusks, and beautiful coral. It's open from 10am to 6pm, and is located about 40 miles south on Highway 1 in Monterey just off of Steinbeck's Cannery Row. For aquarium information call (408) 375-3333. Shakespeare Santa Cruz performances include: "A Midsummer Night's Dream" outside in the redwoods (2pm Saturday and Sunday); "Measure for Measure" (Saturday at 8pm); and "Our Town" (7:30 PM on Sunday). The box office can be reached after July 1 at (408)459-4168 and for general information call (408) 459-2121. Bring swimming trunks, tennis rackets, etc. You can get day passes for $2.50 (East Field House, Physical Education Office) to use the recreation facilities on campus. If you have questions regarding registration or accommodations, contact: Jean McKnight, COLT '91, Dept. of Computer Science, UCSC, Santa Cruz, CA 95064. Her emergency phone number is (408) 459-2303, but she prefers E-mail to jean@cs.ucsc.edu or facsimile at (408) 429-0146. COLT '91 PROGRAM General Information: The Registration will be at the reception, 7:00 - 10:00PM Sunday, in the Crown Merrill Multi-Purpose Room. Late Registration, etc., will be near Cowell Dining Hall during the technical sessions. All lectures will be in Cowell Dining Hall. The banquet will be held Tuesday at 6:30PM in Stevenson Dining Hall. There will be computers available, so that the real addicts can check their e-mail. You can access the computer room from the Cowell Dining Hall where the lectures are held. There is a copy center in the Communications Building (8:00 am to 5:00 pm). The workshop has been organized to allow ample time for informal discussion and collaboration. In addition to the regular technical sessions, we are pleased to present two special invited lectures by Tom Cover from Stanford University and Rodney Brooks from MIT. Sunday, August 4th: Reception, 7:00 - 10:00 pm, Crown Merrill Multi-Purpose Room, located in the center of the dorm complex where you are staying. Preregistered attendees can check in at that time. Monday, August 5th Session 1: 9:00 -- 10:20 Tracking Drifting Concepts Using Random Examples by David P. Helmbold and Philip M. Long Investigating the Distribution Assumptions in the Pac Learning Model by Peter L. Bartlett and Robert C. Williamson Simultaneous Learning and Estimation for Classes of Probabilities by Kevin Buescher and P.R. Kumar Learning by Smoothing: a morphological approach by Michael Woonkyung Kim Session 2: 11:00 -- 12:00 Unifying Bounds on the Sample Complexity of Bayesian Learning Using Information Theory and the VC Dimension by David Haussler, Michael Kearns and Robert E. Schapire Generalization Performance of Bayes Optimal Classification Algorithm for Learning a Perceptron by Manfred Opper and David Haussler Probably Almost Bayes Decisions by Paul Fischer, Stefan P o lt, and Hans Ulrich Simon Session 3: 2:00 -- 3:00 Generalization and Learning, invited talk by Tom Cover Session 4: 3:30 -- 4:30 A Geometric Approach to Threshold Circuit Complexity by Vwani Roychowdhury, Kai-Yeung Siu, Alon Orlitsky, and Thomas Kailath Learning Curves in Large Neural Networks by H. Sompolinsky, H.S. Seung, and N. Tishby On the Learning of Infinitary Regular Sets by Oded Maler and Amir Pnueli Impromptu talks: 5:00 -- 6:00 Business Meeting: 8:00 Impromtu talks: 9:00 Tuesday, August 6 Session 5: 9:00 -- 10:20 Learning Monotone DNF with an Incomplete Membership Oracle by Dana Angluin and Donna K. Slonim Redundant Noisy Attributes, Attribute Errors, and Linear-threshold Learning Using Winnow by Nicholas Littlestone Learning in the presence of finitely or infinitely many irrelevant attributes by Avrim Blum, Lisa Hellerstein, and Nick Littlestone On-Line Learning with an Oblivious Environment and the Power of Randomization by Wolfgang Maass Session 6: 11:00 -- 12:00 Learning Monotone k\mu-DNF Formulas on Product Distributions by Thomas Hancock and Yishay Mansour Learning Probabilistic Read-once Formulas on Product Distributions by Robert E. Schapire Learning 2\mu-DNF Formulas and k\mu Decision Trees by Thomas R. Hancock Session 7: 2:00 -- 3:00 Invited talk by Rodney Brooks Session 8: 3:30 -- 4:30 Polynomial-Time Learning of Very Simple Grammars from Positive Data by Takashi Yokomori Relations Between Probabilistic and Team One-Shot Learners by Robert Daley, Leonard Pitt, Mahendran Velauthapillai, Todd Will When Oracles Do Not Help by Theodore A. Slaman and Robert M. Solovay Impromptu talks: 5:00 -- 6:00 Banquet: 6:30 Wednesday, August 7 Session 9: 9:00 -- 10:20 Approximation and Estimation Bounds for Artificial Neural Networks by Andrew R. Barron The VC-Dimension vs. the Statistical Capacity for Two Layer Networks with Binary Weights by Chuanyi Ji and Demetri Psaltis On Learning Binary Weights for Majority Functions by Santosh S. Venkatesh Evaluating the Performance of a Simple Inductive Procedure in the Presence of Overfitting Error by Andrew Nobel Session 10: 11:00 -- 12:00 Polynomial Learnability of Probabilistic Concepts with respect to the Kullback-Leibler Divergence by Naoki Abe, Jun-ichi Takeuchi, and Manfred K. Warmuth A Loss Bound Model for On-Line Stochastic Prediction Strategies by Kenji Yamanishi On the Complexity of Teaching by Sally A. Goldman and Michael J. Kearns Session 11: 2:00 -- 3:40 Improved Learning of AC^0 Functions by Merrick L. Furst, Jeffrey C. Jackson, and Sean W Smith Learning Read-Once Formulas over Fields and Extended Bases by Thomas Hancock and Lisa Hellerstein Fast Identification of Geometric Objects with Membership Queries by William J. Bultman and Wolfgang Maass Bounded degree graph inference from walks by Vijay Raghavan On the Complexity of Learning Strings and Sequences by Tao Jiang and Ming Li The proceedings will be published by Morgan Kaufmann, contact them directly for ordering information. As the program and registration forms are being distributed electronically, please post and/or distribute to your colleagues who might not be on our E-mail list. Updated copies of the conference information, program, and registration forms can be obtained by anonymous ftp. Connect to midgard.ucsc.edu and look in the directory pub/colt.