fulk@cs.rochester.edu (Mark Fulk) (06/09/90)
COLT '90
The Third Workshop on Computational Learning Theory
Stouffer's Rochester Plaza Hotel
Rochester, NY
August 6-8, 1990
Sponsored by ACM SIGACT and SIGART
COLT '90 features 36 papers and one invited address (by Rusins Freivalds
of Latvian State University). Many papers address learnability and
non-learnability, as well as resource consumption and robustness against
bad data in new and existing computational learning models. Other papers
make theoretical comparisons of learning models, or connect learning theory
with work in neural nets and complexity theory. Models considered include
pac-learnability, mistake-bound models, recursion-theoretic inductive
inference, and other new and classical models. This is the largest COLT
program so far, and, in the humble opinion of at least one program
committee member, it is also the best.
The registration fee is $150 ($75 for students). This fee covers a banquet,
reception (August 5), refreshments, and the proceedings. Participants
are expected to find their own lunches. The hotel food is excellent, and
there are several very good restaurants in the immediate area.
The registration deadline for the conference is July 10; this is also
the last date to guarantee a reservation at the conference rate at
the hotel.
Chair and local arrangements: Mark A. Fulk (U. Rochester).
Program committee: John Case (U. Delaware, chair),
Dana Angluin (Yale),
Eric Baum (NEC Research, Princeton)
Shai Ben-David (Technion, Israel),
Mark Fulk (U. Rochester),
David Haussler (UC Santa Cruz),
Leonard Pitt (U. Illinois),
Ronald Rivest (MIT),
Carl Smith (Maryland),
Scott Weinstein (U. Pennsylvania).
Program
Monday, August 6
Session 1, 8:40 - 10:00 am, David Haussler, chair
8:40 Identifying mu-Formula Decision Trees with Queries,
by Thomas R. Hancock
9:00 Learning Switch Configurations,
by Vijay Raghavan and Stephen R. Schach
9:20 Learning Conjunctions of Horn Clauses,
by Dana Angluin, Michael Frazier, and Leonard Pitt
9:40 Exact Identification of Circuits Using Fixed Points of
Amplification Functions,
by Sally Goldman, Michael J. Kearns, and Robert E. Schapire
Session 2, 10:40 - 12:00 am, Leonard Pitt, chair
10:40 Efficient Distribution-free Learning of Probabilistic Concepts,
by Michael Kearns and Robert E. Schapire
11:00 On the Computational Complexity of Approximating Distributions
by Probabilistic Automata,
by Naoki Abe and Manfred K. Warmuth
11:20 A Learning Criterion for Stochastic Rules,
by Kenji Yamanishi
11:40 On the Complexity of Learning Minimum Time-Bounded Turing Machines,
by Ker-I Ko
Session 3, 2:00 - 3:20 pm, Scott Weinstein, chair
2:00 Inductive Inference from Positive Data is Powerful,
by Takeshi Shinohara
2:20 Inductive Identification of Pattern Languages with
Restricted Substitutions,
by Keith Wright
2:40 Pattern Languages Are Not Learnable,
by Robert Schapire
3:00 On Threshold Circuits for Parity,
by Ramamohan Paturi and Michael E. Saks
Session 4, 3:40 - 5:00 pm, Carl Smith, chair
Invited Presentation by Rusins Freivalds,
Latvian State University, Riga
Tuesday, August 7
Session 5, 8:40 - 10:00 am, Eric Baum, chair
8:40 On Learning Ring-Sum-Expansions,
by Paul Fischer and Hans Ulrich Simon
9:00 Learning Functions of k Terms,
by Avrim Blum and Mona Singh
9:20 On the Sample Complexity of Pac-Learning using Random
and Chosen Examples,
by Bonnie Eisenberg and Ronald L. Rivest
9:40 On the Complexity of Learning from Counterexamples of
Membership Queries,
by Wolfgang Maass and Gyorgy Turan
Session 6, 10:40 - 12:00 am, John Case, chair
10:40 Robust Separations in Inductive Inference,
by Mark A. Fulk
11:00 Finite Learning by a "Team",
by Sanjay Jain and Arun Sharma
11:20 Some Problems of Learning with an Oracle,
by Efim B. Kinber
11:40 A Mechanical Method of Successful Scientific Inquiry,
by Daniel N. Osherson, Michael Stob, and Scott Weinstein
Session 7, 2:00 - 3:20 pm, Dana Angluin, chair
2:00 Separating PAC and Mistake-Bound Learning Models over the
Boolean Domain,
by Avrim Blum
2:20 Boosting a Weak Learning Algorithm by Majority,
by Yoav Freund
2:40 On the Sample Complexity of Weak Learning,
by Sally Goldman, Michael J. Kearns, and Robert E. Schapire
3:00 Learning by Distances,
by Shai Ben-David, Alon Itai, and Eyal Kushilevitz
Session 8, 3:40 - 5:00 pm, Ron Rivest, chair
Informal presentations
Wednesday, August 8
Session 9, 8:40 - 10:00 am, Ron Rivest, chair
8:40 The Learnability of Formal Concepts,
by Martin Anthony, John Shawe-Taylor, and Norman Biggs
9:00 A Polynomial Time Algorithm That Learns Two Hidden Unit Nets,
by Eric B. Baum
9:20 Composite Geometric Concepts and Polynomial Predictability,
by Phil Long and Manfred K. Warmuth
9:40 Learning Integer Lattices,
by David Helmbold, Robert Sloan, and Manfred Warmuth
Session 10, 10:40 - 12:00 am, Mark Fulk, chair
10:40 On the Number of Examples and Stages Needed for Learning
Decision Trees,
by Hans Ulrich Simon
11:00 Learning DNF under the Uniform Distribution in Quasi-polynomial Time,
by Karsten Verbeurgt
11:20 Learning via Queries with Teams and Anomalies,
by William I. Gasarch, Efim Kinber, Mark Pleszkoch,
Carl Smith, and Thomas Zeugmann
11:40 Learning via Queries in [+, <],
by William Gasarch, Mark Pleszkoch, and Robert Solovay
Session 11, 2:00 - 3:20 pm, Shai Ben-David, chair
2:00 On the Sample Complexity of Finding Good Search Strategies,
by Pekka Orponen and Russell Greiner
2:20 Minimum Consistent Inference of Random Walks,
by Javed A. Aslam and Ronald L. Rivest
2:40 Aggregating Strategies,
by Volodimir G. Vovk
3:00 A DNA Sequencing Theory,
by Ming Li
Session 12, 3:40 - 5:00 pm, Mark Fulk, chair
Informal presentations
Getting To Rochester
By airplane:
The best airline is USAIR, followed by American. Travellers from outside
the US should consider flying by way of Toronto, Montreal, or Boston,
rather than attempting to make connections in New York. Once in the
Rochester airport, find the Stouffer's courtesy phone (there is one in
each concourse, in the bank of courtesy phones) and call for the shuttle.
They will direct you from there. The shuttle runs from 6:00 a.m. to
midnight, and no flights are scheduled after midnight, so you should not
have to take a taxi; however, if you must, a taxi to the hotel costs
about $14.50.
If you drive from the airport, the simplest, although not most pleasant,
route is: turn right out of the airport entrance onto Brooks Avenue,
going north. Continue on Brooks over the highway and through a
residential neighborhood until Brooks ends at Plymouth Avenue, by
the Genesee river. Turn left and take Plymouth north to Ford Street,
where it appears to end; turn right and then immediately left onto
Exchange Street. Continue north on Exchange to downtown. You will
pass under a highway; three lights further north Exchange becomes
State Street as it crosses West Main Street. The hotel is on your right,
shortly after Main Street.
Driving:
If coming from the west on Interstate 90, take exit 47 (Leroy and I-490).
Continue east on I-490 to downtown Rochester. Take exit 13 (Plymouth Avenue
and the Inner Loop), veering right to get Plymouth. Turn right (south)
on Plymouth; take the next left (Church), drive two blocks to State Street,
then turn right. The hotel will be to your left within a hundred yards.
If coming from the east on I-90, take exit 45 (Victor and I-490). Continue
west to downtown Rochester; take exit 11 to Clinton Avenue North. Take the
second left onto Broad Street, go through three lights, cross the river, and
take the first right after the river onto Exchange Street. Go north on
Exchange through one light (Main Street), at which it becomes State Street.
The hotel will be on your right shortly after Main Street.
If coming from the south on I-390, keep left (on I-390, to the Airport and
Greece) at the I-390/590 split. Take exit 16 to East and West Henrietta
Roads; the exit comes up right after the split. Keep going straight through
the light at the top of the ramp, bear right at the fork, and turn right at
the light on West Henrietta Road. You will go through about five lights
before you each Ford Street; once there, turn left to cross the Genesee
River. Take the first right after the bridge (Exchange Street); continue
north to downtown. You will pass under a highway; three lights later, at
Main Street, Exchange becomes State Street; the hotel is another few
hundred feet on the right.
Hotel Reservations
You may register by sending the form below, or by calling 1-716-546-3450.
The Stouffer's 800 number, 1-800-HOTELS1, can take your reservation but
does not know about the conference rate. Your reservation must be received
by July 10, 1990, in order to guarantee the conference rate.
If enough students request, we will form quads to save costs. We will
use the attributes male/female and smoking/non-smoking to form the quads.
Any students requesting this service should let us know by July 1, so that
we have enough time to process the request. Conference funds may be used
to pay for the odd spaces.
Family Activities
The New York wine country is one hour south of Rochester. Niagara Falls
is one and a half hours west. There are a number of beaches along Lake
Ontario; Hamlin Beach State Park, half an hour west, is probably the best.
Durand Eastman Park is surprisingly wild considering that it is officially
in the city limits. There are some parks and a zoo along the Genesee
River gorge north of downtown; the (pedestrian) Pont des Rennes offers a
nice view of the falls, and is just a few blocks from the hotel.
Rochester has several good museums: Eastman House, the home of the
founder of Kodak, has tours; it also houses the International Museum
of Photography and the Dryden Theatre. The Toronto Film Festival will
be at the Dryden on the first day of the conference. The University's
Memorial Art Gallery contains a fine collection of Mannerist paintings.
The Rochester Museum and Science Center has a planetarium and various
exhibits.
The Eastman School of Music has a regular schedule of concerts. Other
local arts groups include the GeVa theatre and The Bucket dance group.
The Genesee Country Museum is about 45 minutes south of town, in Mumford;
it is a large collection of eighteenth and nineteenth century buildings
and houses, including blacksmiths, breweries, and the like. There are
almost always exhibits of crafts from the period covered, and are also
frequent farm fairs. The country museum is popular with children; we
will organize a trip to it for families if enough people express an
interest. Normally, admission is $4.50/adult, free for small children.
Third Annual Workshop on Computational Learning Theory
Rochester, NY
Registration Form
Name _________________________________________________________
Affiliation __________________________________________________
Electronic Mail Address ______________________________________
Address ______________________________________________________
______________________________________________________________
______________________________________________________________
Telephone Number _____________________________________________
Are you a student? _________
Would you like to be grouped with two roommates? _____
If yes, indicate: Smoker/Nonsmoker _______ Male/Female_______
Are you (or your family) interested in a day trip to the
Genesee Country Museum? __________
If you would like extra banquet tickets ($35),
please indicate how many _____
Indicate any dietary restrictions:
Kosher _____ Vegetarian _____ Other ____________________
Registration Fee: $150 ____ $75 (students only) ____
Total enclosed (checks or money orders only please): __________
Mail to: COLT '90
c/o Mark Fulk
Computer Science Department
University of Rochester
Rochester, NY 14627
Room Reservation for COLT '90, August 6-8
Name: _________________________________________________________
Company: ______________________________________________________
Address: ______________________________________________________
_______________________________________________________________
_______________________________________________________________
_______________________________________________________________
Telephone number: _____________________________________________
Sharing room with: ____________________________________________
Arrival date and time: ________________________________________
Number of nights to reserve: __________________________________
To guarantee your reservation, a credit card (American Express,
Visa, Mastercard, Discover, Diner's Club, or Carte Blanche):
___________________________________________ Expires: __________
Signature: ____________________________________________________
You may also send a check or money order for the first night's
rate in order to guarantee your reservation.
Please indicate your room preference:
Single ($74/night) ____ Double ($80/night) ____
Triple ($86/night) ____ Quad ($92/night) ____
Club Floor ($104/night) ____
One Bedroom Suite ($225/night) ___
Two Bedroom Suite ($315/night) ___
Quoted prices do not include 11% state sales tax. Checkout
time is 1:00 p.m.; rooms become available for checkin at
3:00 p.m. Your deposit is refundable only if you cancel 48
hours in advance. Be sure to get a cancellation number.
Mail to: Stouffer Rochester Plaza
70 State St.
Rochester, NY 14614