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
lind@PERRON.MATH.WASHINGTON.EDU (Doug Lind) (10/20/90)
PRELIMINARY ANNOUCEMENT
CONFERENCE ON 'ARITHMETICS AND SYMBOLIC DYNAMICS'
September 9-14, 1991 at
Centre International de Rencontres Mathematiques
(Luminy-Marseille)
SCIENTIFIC ORGANIZING COMMITTEE:
M. Keane, Delft University
P. Liardet, Provence University
D. Lind, University of Washington
D. Perrin, LIPT Paris 7
K. Schmidt, Warwick University
J-P. Thouvenot, Paris 7
For further information, contact:
P. Liardet
Universite de Provence
Case 96, 3 Pl. Victor Hugo
F-13331 Marseille cedex 3
e-mail: liardet@frccup51.bitnetweiss@MATH.PSU.EDU (Howie Weiss) (11/01/90)
SIXTH CONFERENCE IN
GEOMETRIC RIGIDITY AND HYPERBOLIC DYNAMICS
will be held at
THE PENNSYLVANIA STATE UNIVERSITY
STATE COLLEGE, PENNSYLVANIA, U.S.A.
March 16-23, 1991
The conference is partially supported by the Pennsylvania State University
and the University of Michigan. Other outside support is anticipated.
The main theme of the conference is the synthesis of several branches of
dynamics (smooth dynamical systems, ergodic theory, symplectic dynamics) with
other mathematical disciplines (Lie groups and symmetric spaces, differential
geometry, group representations, number theory), centered around the
phenomenon of rigidity.
TOPICS TO BE COVERED
1. Smooth actions of ``large '' groups and cocycles over group actions;
geometric and dynamical aspects of foliation theory.
2. Rigidity and critical regularity of invariant geometric structures for
smooth dynamical systems.
3. Manifolds of negative and non-positive curvature; rigidity phenomena,
harmonic maps, Laplacian.
4. Hyperbolic and normally hyperbolic actions of abelian and other ``small''
groups; rigidity of algebraic dynamical systems.
5. Selected applications of dynamics and rigidity to number theory.
6. Some aspects of smooth ergodic theory, billiards, dynamical systems with
singularities, and strange attractors.
The following is an incomplete list of mathematicians who will participate
in the conference:
D. Anosov, W. Ballman, M. Brin, K. Burns, E. Calabi, P. Eberlein,
A. Fathi, J. Feldman, R. Feres, L. Flaminio, E. Ghys, M. Gromov,
U. Hamenstaedt, B. Hasselblatt, S. Hurder, A. Katok, S. Katok,
G. Knieper, F. Labourie, F. Ledrappier, J. Lewis, G. Margulis,
Y. Pesin, P. Sarnak, R. Spatzier, G. Thorbergsson, H. Weiss
M. Wojtkowski, R. Zimmer
ORGANIZERS: A. Katok, R. Spatzier, R. Zimmer
FOR INFORMATION CONTACT: Secretary: Rosemary Manning (814) 865 7527
E-Mail address is rigidity@math.psu.eduKITCH@YKTVMV.BITNET (Bruce Kitchens) (01/24/91)
"Symbolic Dynamics and Its Applications"
July 28 - August 2, 1991
Yale University
In part to honor Dr. Roy Adler, IBM Research, for his many important
contributions to the subject.
SPEAKERS WILL INCLUDE: Jon Ashley, Mike Boyle, Elise Cawley, Leo
Flatto, David Handelman, Mike Keane, Linda Keen, Rick Kenyon,
Doug Lind, Brian Marcus, Bill Parry, Klaus Schmidt, Caroline Series,
Paul Trow, Selim Tuncel, Jack Wagoner, Benjamin Weiss, Susan Williams
ORGANIZING COMMITTEE: Ethan Coven (Wesleyan University),
Shizuo Kakutani (Yale University),
Bruce Kitchens (IBM Research-Yorktown Heights)
Brian Marcus (IBM Research-Almaden),
Don Ornstein (Stanford University),
Benjamin Weiss (The Hebrew University)
For Further Information, Contact:
Bruce Kitchens,
IBM Watson Research Center,
PO Box 218,
Yorktown Heights, NY 10598, USA,
or e-mail: kitch@ibm.com
*********************************************************************
Attendance and Housing
We have reserved a block of rooms in the Yale Colleges. The cost
will be about $115 for the duration of the conference. Breakfast
and lunch will be available for about $10 per day. There will
also be local motels available. We have applied for financial
support to help offset these costs.
If you are interested in attending the conference or would like to
receive more information, please complete the following form
and return it to: Bruce Kitchens, IBM Watson Research Center,
PO Box 218, Yorktown Heights, NY 10598, USA. You may also respond
by e-mail to kitch@ibm.com.
******************************************************************
I am interested in attending the conference
Symbolic Dynamics and its Applications.
Name ____________________________________________________________
Address__________________________________________________________
__________________________________________________________
__________________________________________________________
__________________________________________________________
e-mail address___________________________________________________scott@MATH.SUNYSB.EDU (Scott Sutherland) (02/26/91)
TOPOLOGICAL METHODS in MODERN MATHEMATICS
A Symposium in Honor of John Milnor's Sixtieth Birthday
SUNY at Stony Brook, Stony Brook, NY June 14-21 1991
Speakers will include:
Hyman Bass, Jean-Michel Bismut, Spencer Bloch, Raoul Bott,
Bodil Branner, Adrien Douady, Yakob Eliashberg, Henri Gillet,
Wu-Chung Hsiang, John Hubbard, Vaughn Jones, Curt McMullen,
S.P. Novikov, Graeme Segal, Lawrence Siebenmann, I. M. Singer,
James Stasheff, Bernard Tessier, William Thurston, Edward Witten.
Main topics:
Global Geometry, Topology and Mathematical Physics (6/15-6/16)
Algebraic Geometry and K-theory (6/17-6/18)
Dynamical Systems (6/19-6/21)
Four days of workshops and minicourses (6/22-6/25) will follow
the symposium.
Graduate students are encouraged to attend. Some support is
available for travel and accomodations.
Scientific Committee: H. Bass, M. Gromov, L. Siebenmann, D. Sullivan
Organizing Committee: L. R. Goldberg (CUNY), H. B. Lawson, Jr.,
D. McDuff, A. V. Phillips.
Information: contact the committee or
Ms. Gerri Sciulli,
Institute for Mathematical Sciences,
SUNY, Stony Brook NY 11794-3660
516-632-7318;
email: ims@math.sunysb.edu
gsciulli@sbccmail.bitnet