COLT '93 Sixth ACM Conference on Computational Learning Theory Monday, July 26 through Wednesday, July 28, 1993 University of California, Santa Cruz, California EARLY REGISTRATION DEADLINE: JUNE 15 The workshop will be held on campus, which is hidden away in the redwoods on the Pacific coast of Northern California. The workshop is sponsored by the ACM Special Interest Group on Algorithms and Computation Theory (SIGACT) and the ACM Special Interest Group on Artificial Intelligence (SIGART). The long version of this document is available by anonymous ftp from ftp.cse.ucsc.edu. To ftp the document you do the following: step 1) ftp ftp.cse.ucsc.edu, and login as "anonymous", 2) cd pub/colt, 3) binary, 4) get colt93.registration.ps. REGISTRATION INFORMATION ------------------------ Please fill in the information needed on the registration sheet Make your payment by check or international money order, in U.S. dollars and payable through a U.S. bank, to COLT '93. Mail the form together with payment (by June 15 to avoid the late fee) to: COLT '93 Dept. of Computer Science University of California Santa Cruz, California 95064 ACCOMMODATIONS AND DINING Accommodation fees are $57 per person for a double and $70 for a single per night at the College Eight Apartments. Cafeteria style breakfast (7:45 to 8:30am), lunch (12:30 to 1:30pm), and dinner (6:00 to 7:00pm) will be served in the College Eight Dining Hall. Doors close at the end of the time indicated, but dining may continue beyond this time. The first meal provided is dinner on the day of arrival and the last meal is lunch on the day you leave. NO REFUNDS can be given after June 15. Those with uncertain plans should make reservations at an off-campus hotel. Each attendee should pick one of the five accomdation packages. For shorter stays, longer stays, and other special requirements, you can get other accommodations through the Conference Office. Make reservations directly with them at (408)459-2611, fax (408)459-3422, and do this soon as on-campus rooms for the summer fill up well in advance. Off-campus hotels include the Dream Inn (408)426-4330 and the Holiday Inn (408)426-7100. Questions: e-mail colt93@cse.ucsc.edu, fax (408)429-4829. Confirmations will be sent by e-mail. Anyone needing special arrangements to accommodate a disability should enclose a note with their registration. If you don't receive confirmation within three weeks of payment, let us know. Get updated versions of this document by anonymous ftp from ftp.cse.ucsc.edu. CONFERENCE REGISTRATION FORM (see accompanying information for details) Name: ___________________________________ Affiliation: ___________________________________ Address: ___________________________________ City: ________________ State: ____________ Zip: ________________ Country: ____________________ Telephone: (____) ________________ Email: ________________________ The registration fee includes a copy of the proceedings. ACM/SIG Members: $165 (with banquet) $___________ Non-Members: $185 (with banquet) $___________ Late: $220 (postmarked after June 15) $___________ Full time students: $80 (no banquet) $___________ Extra banquet tickets: ___ (quantity) x $18 = $___________ How many in your party have dietary restrictions? Vegetarian: ___________ Other: ___________ Shirt size, please circle one: small medium large x-large ACCOMODATIONS: Pick one package: _____ Package 1: Sun, Mon, Tue nights: $171 double, $210 single. _____ Package 2: Sat, Sun, Mon, Tue nights: $228 double, $280 single. _____ Package 3: Sun, Mon, Tues, Wed nights: $228 double, $280 single. _____ Package 4: Sat, Sun, Mon, Tue, Wed nights: $285 double, $350 single. ______Other housing arrangement. Each 4-person apartment has a living room, a kitchen, two common bathrooms, and either four single separate rooms, two double rooms, or two single and one double room. We need the following information to make room assignments: Gender (M/F): __________ Smoker (Y/N): __________ Roommate Preference: ____________________ AMOUNT ENCLOSED: Registration $___________________ Banquet tickets $___________________ Accommodations $___________________ TOTAL $___________________ Mail this form together with payment (by June 15 to avoid the late fee) to: COLT '93, Dept. of Computer Science, Univ. California, Santa Cruz, CA 95064 COLT '93 --- Conference Schedule Sixth ACM Conference on Computational Learning Theory Monday, July 26 through Wednesday, July 28, 1993 University of California, Santa Cruz, California SUNDAY, JULY 25 4:00 - 6:00 pm, Housing Registration, College Eight Satellite Office. 7:00 - 10:00 pm, Reception, Oakes Learning Center. Preregistered attendees may check in at the reception. Note: All technical sessions will take place in Oakes 105 . MONDAY, JULY 26 Session 1: Learning with Queries Chair: Dana Angluin 8:20-8:40 Learning Sparse Polynomials over Fields with Queries and Counterexamples. Robert E. Schapire and Linda M. Sellie 8:40-9:00 Learning Branching Programs with Queries. Vijay Raghavan and Dawn Wilkins 9:00-9:10 Linear Time Deterministic Learning of k-term DNF. Ulf Berggren 9:10-9:30 Asking Questions to Minimize Errors. Nader H. Bshouty, Sally A. Goldman, Thomas R. Hancock, and Sleiman Matar 9:30-9:40 Parameterized Learning Complexity. Rodney G. Downey, Patricia Evans, and Michael R. Fellows 9:40-10:00 On the Query Complexity of Learning. Sampath K. Kannan 10:00 - 10:30 BREAK Session 2: New Learning Models and Problems Chair: Sally Goldman 10:30-10:50 Teaching a Smarter Learner. Sally A. Goldman and H. David Mathias 10:50-11:00 Learning and Robust Learning of Product Distributions. Klaus-U. Hoffgen 11:00-11:20 A Model of Sequence Extrapolation. Philip Laird, Ronald Saul and Peter Dunning 11:20-11:30 On Polynomial-Time Probably Almost Discriminative Learnability. Kenji Yamanishi 11:30-11:50 Learning from a Population of Hypotheses. Michael Kearns and Sebastian Seung 11:50-12:00 On Probably Correct Classification of Concepts. S.R. Kulkarni and O. Zeitouni 12:00 - 1:40 LUNCH Session 3: Inductive Inference; Neural Nets Chair: Bob Daley 1:40-2:00 On the Structure of Degrees of Inferability. Martin Kummer and Frank Stephan 2:00-2:20 Language Learning in Dependence on the Space of Hypotheses. Steffen Lange and Thomas Zeugmann 2:20-2:30 On the Power of Sigmoid Neural Networks. Joe Kilian and Hava T. Siegelmann 2:30-2:40 Lower Bounds on the Vapnik-Chervonenkis Dimension of Multi-layer Threshold Networks. Peter L. Bartlett 2:40-2:50 Average Case Analysis of the Clipped Hebb Rule for Nonoverlapping Perceptron Networks. Mostefa Golea and Mario Marchand 2:50-3:00 On the Power of Polynomial Discriminators and Radial Basis Function Networks. Martin Anthony and Sean B. Holden 3:00 - 3:30 BREAK 3:30-4:30 Invited Talk by Geoffrey Hinton The Minimum Description Length Principle and Neural Networks. 4:45 - ? Impromptu talks, open problems, etc. 7:00 - 10:00 pm, Banquet, barbeque pit outside Porter Dining Hall. TUESDAY, JULY 27 Session 4: Inductive Inference Chair: Rolf Wiehagen 8:20-8:40 The Impact of Forgetting on Learning Machines. Rusins Freivalds, Efim Kinber, and Carl H. Smith 8:40-8:50 On Parallel Learning. Efim Kinber, Carl H. Smith, Mahendran Velauthapillai, and Rolf Wiehagen 8:50-9:10 Capabilities of Probabilistic Learners with Bounded Mind Changes. Robert Daley and Bala Kalyanasundaram 9:10-9:20 Probability is More Powerful than Team for Language Identification from Positive Data. Sanjay Jain and Arun Sharma 9:20-9:40 Capabilities of Fallible FINite Learning. Robert Daley, Bala Kalyanasundaram, and Mahendran Velauthapillai 9:40-9:50 On Learning in the Limit and Non-uniform (epsilon, delta)-Learning. Shai Ben-David and Michal Jacovi 9:50 - 10:20 BREAK Session 5: Formal Languages, Rectangles, and Noise Chair: Takeshi Shinohara 10:20-10:40 Learning Fallible Deterministic Finite Automata. Dana Ron and Ronitt Rubinfeld 10:40-11:00 Learning Two-Tape Automata from Queries and Counterexamples. Takashi Yokomori 11:00-11:10 Efficient Identification of Regular Expressions from Representative Examples. Alvis Brazma 11:10-11:30 Learning Unions of Two Rectangles in the Plane with Equivalence Queries. Zhixiang Chen 11:30-11:50 On-line Learning of Rectangles in Noisy Environments. Peter Auer 11:50-12:00 Statistical Queries and Faulty PAC Oracles. Scott Evan Decatur 12:00 - 1:40 LUNCH Session 6: New Models; Linear Thresholds Chair: Wray Buntine 1:40-2:00 Learning an Unknown Randomized Algorithm from its Behavior. William Evans, Sridhar Rajagopalan, and Umesh Vazirani 2:00-2:20 Piecemeal Learning of an Unknown Environment. Margrit Betke, Ronald L. Rivest, and Mona Singh 2:20-2:40 Learning with Restricted Focus of Attention. Shai Ben-David and Eli Dichterman 2:40-2:50 Polynomial Learnability of Linear Threshold Approximations. Tom Bylander 2:50-3:00 Rate of Approximation Results Motivated by Robust Neural Network Learning. Christian Darken, Michael Donahue, Leonid Gurvits, and Eduardo Sontag 3:00-3:10 On the Average Tractability of Binary Integer Programming and the Curious Transition to Generalization in Learning Majority Functions. Shao C. Fang and Santosh S. Venkatesh 3:10 - 3:30 BREAK 3:30-4:30 Invited Talk by John Grefenstette Genetic Algorithms and Machine Learning 4:45 - ? Impromptu talks, open problems, etc. 7:00 - 8:30 Poster Session and Dessert Oakes Learning Center 8:30 - 10:00 Business Meeting Oakes 105 WEDNESDAY, JULY 28 Session 7: Pac Learning Chair: Yishay Mansour 8:20-8:40 On Learning Visual Concepts and DNF Formulae. Eyal Kushilevitz and Dan Roth 8:40-9:00 Localization vs. Identification of Semi-Algebraic Sets. Shai Ben-David and Michael Lindenbaum 9:00-9:20 On Learning Embedded Symmetric Concepts. Avrim Blum, Prasad Chalasani, and Jeffrey Jackson 9:20-9:30 Amplification of Weak Learning Under the Uniform Distribution. Dan Boneh and Richard J. Lipton 9:30-9:50 Learning Decision Trees on the Uniform Distribution. Thomas R. Hancock 9:50 - 10:20 BREAK Session 8: VC dimension, Learning Complexity, and Lower Bounds Chair: Sebastian Seung 10:20-10:40 Bounding the Vapnik-Chervonenkis Dimension of Concept Classes Parameterized by Real Numbers. Paul Goldberg and Mark Jerrum 10:40-10:50 Occam's Razor for Functions. B.K. Natarajan 10:50-11:00 Conservativeness and Monotonicity for Learning Algorithms. Eiji Takimoto and Akira Maruoka 11:00-11:20 Lower Bounds for PAC Learning with Queries. Gyorgy Turan 11:20-11:40 On the Complexity of Function Learning. Peter Auer, Philip M. Long, Wolfgang Maass, and Gerhard J. Woeginger 11:40-12:00 General Bounds on the Number of Examples Needed for Learning Probabilistic Concepts. Hans Ulrich Simon NOON: Check-out of Rooms 12:00 - 1:40 LUNCH Session 9: On-Line Learning Chair: Kenji Yamanishi 1:40-2:00 On-line Learning with Linear Loss Constraints. Nick Littlestone and Philip M. Long 2:00-2:10 The `Lob-Pass' Problem and an On-line Learning Model of Rational Choice. Naoki Abe and Jun-ichi Takeuchi 2:10-2:30 Worst-case Quadratic Loss Bounds for a Generalization of the Widrow-Hoff Rule. Nicolo Cesa-Bianchi, Philip M. Long, and Manfred K. Warmuth 2:30-2:40 On-line Learning of Functions of Bounded Variation under Various Sampling Schemes. S.E. Posner and S.R. Kulkarni 2:40-2:50 Acceleration of Learning in Binary Choice Problems. Yoshiyuki Kabashima and Shigeru Shinomoto 2:50-3:10 Learning Binary Relations Using Weighted Majority Voting. Sally A. Goldman and Manfred K. Warmuth 3:10 CONFERENCE ENDS 3:10 - ? Last fling on the Boardwalk.