COLT '91 conference program

[David Haussler]

CONFERENCE PROGRAM FOR COLT '91 : PLEASE POST AND DISTRIBUTE

     Workshop on Computational Learning Theory
     Monday, August 5 through Wednesday, August 7, 1991
     University of California, Santa Cruz, California

PROGRAM:

    Sunday, August 4th:

Reception, 7:00 - 10:00 pm, Crown Merrill Multi-Purpose Room

    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 Polt, 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



General Information:

The workshop will be held on the UCSC 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. Conference and room registration:  Forms can be obtained by anonymous 
FTP, connect to midgard.ucsc.edu and look in the directory pub/colt.
Alternatively, send E-mail to "colt at cis.ucsc.edu" for instructins on
obtaining the forms by electronic mail.  Fill out the forms and return
them 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.

2. 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.

3. 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.

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 at 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 at cs.ucsc.edu or facsimile at (408) 429-0146.

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.

LaTex versions 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.