2nd EUROPEAN CONFERENCE ON COMPUTATIONAL LEARNING THEORY EUROCOLT'95 MARCH 13-15, 1995, BARCELONA, SPAIN PROGRAM RECEPTION/REGISTRATION: Sunday, March 12, from 18:00 to 22:00 at the C atedra Gaud SESSION 1: Monday, March 13, Morning Chair: Paul Vit anyi 9:00--9:50 The discovery of algorithmic probability: A guide for the programming of true creativity (Invited Lecture), R.J. Solomonoff (Oxbridge Research, USA) 9:50--10:15 A decision-theoretic generalization of on-line learning and an application to boosting , Y. Freund, R.E. Schapire (AT T Bell Labs) 10:15--10:40 Online learning versus offline learning , S. Ben-David (Technion), E. Kushilevitz (Technion), Y. Mansour (Tel Aviv Univ.) 10:40--11:15 Break SESSION 2: Monday, March 13, Morning Chair: Nicola Cesa-Bianchi 11:15--11:40 Learning distributions by their density levels - a paradigm for learning without a teacher , S. Ben-David, M. Lindenbaum (Technion) 11:40--12:05 Tight worst-case loss bounds for predicting with expert advice , D. Haussler, J. Kivinen, M.K. Warmuth (UCSC) 12:05--12:30 On-line maximum likelihood prediction with respect to general loss functions K. Yamanishi (NEC Research, Princeton) LUNCH: Starting at 13:00 SESSION 3: Monday, March 13, Afternoon Chair: Rusins Freivalds 14:30--14:55 Power of procrastination in inductive inference: How it depends on used ordinal notations , A. Ambainis (Univ. Latvia) 14:55--15:20 Learnability of Kolmogorov-easy circuit expressions via queries , J.L. Balcazar (UPC, Barcelona), H. Buhrman (UPC Barcelona/CWI), M. Hermo (Univ. Pa s Vasco) 15:20--15:45 Trading monotonicity demands versus mind changes , S. Lange (HTWK Leipzig), T. Zeugmann (Kyushu Univ.) 15:45--16:20 Break SESSION 4: Monday, March 13, Afternoon Chair: Ricard Gavald a 16:20--16:45 Learning recursive functions from approximations , J. Case (Univ. Delaware), S. Kaufmann (Univ. Karlsruhe), E. Kinber (Univ. Delaware), M. Kummer (Univ. Karlsruhe), 16:45--17:10 On the intrinsic complexity of learning , R. Freivalds (Univ. Latvia), E. Kinber (Univ. Delaware), C.H. Smith (Univ. Maryland) 17:10--17:35 The structure of intrinsic complexity of learning , S. Jain (Nat. Univ. Singapore), A. Sharma (Univ. New S-Wales, Australia) 17:35--18:00 Kolmogorov numberings and minimal identification , R. Freivalds (Univ. Latvia), S. Jain (Nat. Univ. Singapore) RUMP SESSION: From 18:00 to 19:00 BUSINESS MEETING: From 20:00 to 21:30 SESSION 5: Tuesday, March 14, Morning Chair: Ming Li 9:00--9:50 Stochastic complexity in learning (Invited Lecture), J. Rissanen (IBM Almaden Research Center, USA) 9:50--10:15 Function learning from interpolation , M. Anthony (LSE, London), P. Bartlett (ANU, Canberra, Australia) 10:15--10:40 Approximation and learning of convex superpositions , L. Gurvits (Siemens Res, Princeton), P. Koiran (DIMACS, Rutgers Univ.) 10:40--11:15 Break SESSION 6: Tuesday, March 14, Morning Chair: Jorma Rissanen 11:15--11:40 Minimum description length estimators under the optimal coding scheme , V.G. Vovk (Research Council Cybernetics, Moscow) 11:40--12:05 MDL learning of unions of simple pattern languages from positive examples , P. Kilpel ainen, H. Mannila, E. Ukkonen (Univ. Helsinki) 12:05--12:30 A note on the use of probabilities by mechanical learners , E. Martin, D. Osherson (IDIAP, Switzerland) LUNCH: Starting at 13:00 SESSION 7: Tuesday, March 14, Afternoon Chair: Hans-Ulrich Simon 14:30--14:55 Characterizing rational versus exponential learning curves , D. Schuurmans (Univ. Toronto) 14:55--15:20 Is Pocket algorithm optimal? , M. Muselli (CNR, Italy) 15:20--15:45 Some theorems concerning the free energy of (un)constrained stochastic hopfield neural networks , J. van den Berg, J.C. Bioch (Erasmus Univ.) 15:45--16:20 Break SESSION 8: Tuesday, March 14, Afternoon Chair: Wolfgang Maass 16:20--16:45 A space-bounded learning algorithm for axis-parallel rectangles , F. Ameur (H.Nixdorf Inst/Univ. Paderborn) 16:45--17:10 Learning decision lists and trees with equivalence queries , H.-U. Simon (Univ. Dortmund) SIGHTSEEING: From 17:10 to 21:00 BANQUET: Starting at 21:00 SESSION 9: Wednesday, March 15, Morning Chair: Kenji Yamanishi 9:00--9:50 Bounding VC dimension of Neural Networks: Progress and Prospects (Invited Lecture) , Marek Karpinski (Bonn Univ., Germany), Angus Mcintyre (Oxford University, UK) 9:50--10:15 Average case analysis of a learning algorithm for -DNF expressions , M. Golea (Univ. Ottawa) 10:15--10:40 Learning by extended statistical queries and its relation to PAC learning , E. Shamir, C. Shwartzman (Hebrew Univ.) 10:40--11:15 Break SESSION 10: Wednesday, March 15, Morning Chair: Martin Anthony 11:15--11:40 Typed pattern languages and their learnability , T. Koshiba (Fujitsu Labs, Kyoto) 11:40--12:05 Learning behaviors of automata from shortest counterexamples , F. Bergadano, S. Varricchio (Univ. Catania) 12:05--12:30 Learning of regular expressions by pattern matching , A. Brazma (Univ. Latvia) 12:30--12:55 The query complexity of learning some subclasses of context-free grammars , C. Domingo, V. Lavin (UPC, Barcelona) LUNCH: Starting at 13:00 END OF CONFERENCE Conference Information Location: Barcelona is a city of about 3 million people located on Spain's Mediterranean shore. Founded by the Romans, Barcelona has been for long a center of culture and arts. Fine Romanesque art and architecture, from the middle ages, can be found in Barcelona and surrounding Catalonia. At the turn of the century, Barcelona was a great center of art nouveau. Among its many contributors, the names of Gaudi , Picasso, Dali , Miro or Tapies have gained universal respect, and their works can be admired in the streets and local museums. Today, Barcelona is a vibrant, pulsating city offering a varied cultural life, many shopping areas, and a great variety of restaurants. On the occasion of hosting of 1992 Olympic Games, the city went through large urbanistic changes, and the remodelled seafront areas are now major attractions. Conference Site: The conference will be held at the North Campus of the Universitat Polit ecnica de Catalunya (UPC). To reach it coming from downtown, take the subway line 3 (green), direction Zona Universit aria, to the second last stop (Palau Reial), then follow the signs; total travel time is about 30 minutes. Formal sessions will take place at the Aula Master of the North Campus. Rump sessions will be scheduled at the conference and may take place in a different room. Invited Lectures: There will be invited lectures by Ray Solomonoff (Oxbridge Research), Jorma Rissanen (IBM Almaden), and Angus McIntyre (Oxford Univ.) Social Program: Sunday Night: Reception and registration at the Catedra Gaudi , Avda. Pedralbes 7, 18:00---22:00. This is near the conference site. Coming from downtown, take the subway line 3 (green) to Maria Cristina stop, then follow the signs. Monday Night: Business meeting at the conference site, 20:00--21:30. Tuesday Night: Banquet at El Gran Cafe , starting at 21:00. The Cafe is located in Aviny o 9, a few minute walk from the conference hotels. Weather: Weather in March is usually sunny but be prepared for rain. Day time temperature should be between C and C. Getting there: There are trains running every 30 minutes from the airport to Pla c a Catalunya, the central square of Barcelona close to the conference hotels. Travel time is about 25 minutes. There is also an Airport Bus linking the airport terminals to Pla c a Catalunya. A taxi from the airport to the hotels should cost 2500--3000 Pta, on normal traffic conditions. Accommodation Reservations have been made in the following three hotels: Hotel Catalunya (**): Santa Anna, 24. Phone +34-3-301-9120. Fax +34-3-302-7870. Hotel Montecarlo (***): La Rambla, 124. Phone +34-3-412-0404. Fax +34-3-318-7323. Hotel Rivoli Ramblas (****): La Rambla, 128. Phone +34-3-412-0988. Fax +34-3-318-9133. The three of them are quite close to each other in Barcelona's Old Quarter, the liveliest part of the city. The following are the conference prices in Spanish Pesetas (Pta), including VAT. For Catalunya and Rivoli, these prices also include breakfast. Price Catalunya Montecarlo Rivoli Single 3250 6740 n/a Double 4500 9630 13900 Double, 4050 7560 10700 one occup. For reservations, use the procedure described under Registration and hotel reservation , or send a fax directly to the hotel. The hotels are offering special conference prices (conditioned on a minimum occupancy), so make sure you mention EuroCOLT'95 if you contact them directly. Early reservation is recommended. The conference organization does not handle hotel payments. Please pay to the hotels directly when departing. They will accept major credit cards. Registration Hotel Reservation In order of preference: WWW: Fill in the registration form at http://goliat.upc.es/ eurocolt/reg-form.html E-mail: Get the source of this brochure by anonymous ftp, as described below. Fill in the registration form and e-mail it to eurocolt@lsi.upc.es Or else: Fill in the registration form below and send it by fax or air mail to the organizers. Your registration will be confirmed upon receipt of your payment. Payment The conference fee includes proceedings, lunches for three days, and all social events. lcc Before After Price (in Pta) Feb. 10 Feb. 10 Normal Conference Fee 30000 34000 Student Fee 15000 17000 Extra Banquet Ticket 3000 3500 Extra proceedings will be available on site and cost about 7000 Pta each. Transfer the amount of your registration ( not hotel) to: l Account Name: EuroCOLT'95 Bank: Caixa d'Estalvis i Pensions de Barcelona Account : 2100--0797--91--0200096977 Combining NeuroCOLT meeting with EuroColt'95: The 1st yearly meeting of the EU ESPRIT NeuroCOLT Working Group is planned back-to-back with EuroColt'95 in Barcelona, March 9--11. Participants can arrange the same hotels and joint travel at their convenience. For more information WWW: Connect to http://goliat.upc.es/ eurocolt/info.html ftp: login as anynomous to bloom.upc.es , go to directory pub/eurocolt E-mail: eurocolt@lsi.upc.es Or else: contact the organizers at l Ricard Gavalda -- EuroCOLT'95 Dept. of Software (LSI) Universitat Politecnica de Catalunya Pau Gargallo 5 08028 Barcelona, Spain Phone: +34-3-401-7008 Fax: +34-3-401-7014 E-mail: gavalda@lsi.upc.es Acknowledgments History and Sponsors: The previous and inaugural European Conference on Computational Learning Theory was held 20--22 December 1993 at Royal Holloway, University of London. The EuroCOLT'95 conference is sponsored by the EATCS, by the European Union through NeuroCOLT ESPRIT Working Group Nr. 8556, by IFIP through SSGFCS WG 14.2., and by Universitat Polit ecnica de Catalunya. Local Arrangements Chairs: Ricard Gavald a (UPC, Barcelona), Felipe Cucker (Univ. Pompeu Fabra, Barcelona) Program Committee: M. Anthony (LSE, Univ. London, UK), E. Baum (NEC Research Inst., Princeton), N. Cesa-Bianchi (Univ. Milano, Italy), J. Koza (Stanford Univ, Palo Alto, USA), M. Li (Univ. Waterloo, Canada), S. Muggleton (Oxford University, UK), W. Maass (TU Graz, Austria), J. Rissanen (IBM Almaden, USA), H.-U. Simon (Univ. Dortmund, Germany), K. Yamanishi (NEC, Princeton, USA), L. Valiant (Harvard Univ, Cambridge, USA), P. Vitanyi (Chair, CWI/Univ. Amsterdam, Netherlands), R. Freivalds (Univ. Riga, Latvia) Steering Committee: M. Anthony (LSE, Univ. London, UK), R. Gavald a (UPC, Barcelona), W. Maass (TU Graz, Austria), J. Shawe-Taylor (RHBNC, Univ. London, UK), H.-U. Simon (Univ. Dortmund, Germany) P. Vit anyi (CWI Univ. Amsterdam). REGISTRATION FORM Last name First name Affiliation Mailing address EMail address Vegetarian [ ] [5pt] Registration fee 1.5cm Pta Extra Banquet Ticket(s) 0.2cm Pta Total 3.5cm Pta Your registration will be confirmed upon receipt of payment. [5pt] I want a [ ] Single room [ ] Double room [5pt] [ ] Double room, one occupant in Hotel [ ] Catalunya [ ] Montecarlo [5pt] [ ] Rivoli arriving on March and leaving on March If sharing a double room, name of roommate (or 'anyone'):