Learning for algebraic structures
Speaker(s): Nikolay Bazhenov (Sobolev Institute of Mathematics)
Time: 16:00-17:00 May 8, 2025
Venue: Room 9, Quan Zhai, BICMR
Abstract:
The talk gives an overview of recent results on algorithmic learning for countable families of countable algebraic structures. Within this framework, a learner is a function that, given a finite amount of information about a structure S, outputs a conjecture about the isomorphism type of S. A family of structures K is learnable if there exists a learner that, for any S from K, eventually correctly identifies the isomorphism type of S when given larger and larger amounts of S-data. In this setting, the notion of learnability from atomic diagram admits two useful characterizations: the first one is based on the infinitary logic L_{\omega_1, \omega}, while the second one uses continuous reducibility (which is originated in descriptive set theory). After presenting these characterizations, I plan to discuss learnability from positive information, and related results on models of the positive version of L_{\omega_1, \omega}. The talk is based on joint works with Cipriani, Fokina, Jain, Mustafa, Rossegger, San Mauro, Soskova, Stephan, and Vatev.
Hybrid:
Venue: Quan 9
zoom room: 717 463 6082