- 14/01/2015, 17:00 hrs, Week 1, S17#05-11.

**Frank Stephan**.*Recent Progress on Partial Learning and Related Notions*.

Inductive inference investigates the learnability of classes of r.e. sets or classes of recursive functions from presentations of the data in a natural form. While it is known that the basic criterion of explanatory learning does not permit to learn the class of all recursive functions or all r.e. sets, Osherson, Stob and Weinstein showed that a more general criterion of partial learning permits to learn these two classes. These findings motivated the study of combining partial learning with additional constraints such as confidence, consistency and conservativeness. The present talk provides additional insights on this topic based on recent findings.

This is joint work with Gao Ziyuan and Sandra Zilles

- 21/01/2015, 17:00 hrs, Week 2, S17#05-11.

**Sanjay Jain**.*Parallel learning of automatic classes of languages*.

We introduce and explore a model for parallel learning of families of languages computable by finite automata. In this model, an algorithmic or automatic learner takes on n different input languages and identifies at least m of them correctly. For finite parallel learning, for large enough families, we establish a full characterization of learnability in terms of characteristic samples of languages. Based on this characterization, we show that it is the difference n-m, the number of languages which are potentially not identified, which is crucial. Similar results are obtained also for parallel learning in the limit. We consider also parallel finite learnability by finite automata and obtain some partial results.

This is joint work with Efim Kinber

- 28/01/2015, 17:00 hrs, Week 3, S17#05-11.

**Nazanin Tavana**.*Computable analysis and some applications in metric model theory and measure theory*. Computable analysis is a branch of computability theory studying those real functions and the related sets which can be computed by machines such as digital computers. The increasing demand for reliable software in scientific computation and engineering requires a sound foundation not only of the analytic/numerical but also of the computational aspects of real number computation. The central subject of this talk is one of the approch of computable analysis called "Type Two Theory of Effectivity (TTE)". It is based on definitions of computable real numbers and functions by A. Turing, A. Grzegorczyk and D. Lacombe. First, computability on finite and infinite sequences of symbols is introduced. Then, this kind of computability can be transfered to the other sets by means of names or codes. After, the framework of computability is settled down, we can talk about the effectiveness of some other spaces as metric spaces. At the end, complexity of this approach and its two applications are discussed. One application is for effectiveness in metric model theory and the other one is in measure theory.

- 04/02/2015, 17:00 hrs, Week 4, S17#05-11.

**Wang Wei**.*The definability strength of combinatorial principles*.

In recent years people have extensively studied the provability strength of combinatorial principles related to Ramsey's theorem. In many cases, the provability strength of a combinatorial principle is reflected by its computability strength in the following sense: if solutions of related combinatorial problems can serve as oracles to compute certain complicated sets then the combinatorial principle is of strong provability strength. In this talk, we introduce a different way to analyze strength of combinatorial principles, by examing whether solutions of related problems can help simplify certain definability problems. This approach turns out to be useful in the reverse mathematics of combinatorics.

- 11/02/2015, 17:00 hrs, Week 5, S17#05-11.

**Dilip Raghavan**.*A positive partition relation at the bounding number.*

We show the consistency of the partition relation**b**→ (**b**,α)^{2}, for all α < ω_{1}, relative to the consistency of a measurable cardinal. We indicate how the hypothesis can be significantly weakened to a smaller large cardinal.

This is joint work with Stevo Todorcevic.

- 18/02/2015, 17:00 hrs, Week 6, S17#05-11.

No talk, Chinese New Year Eve.

- 25/02/2015, 17:00 hrs, Recess Week, S17#05-11.

No Talk.

- 04/03/2015, 17:00 hrs, Week 7, S17#05-11.

No Talk.

- 11/03/2015, 17:00 hrs, Week 8, S17#05-11.

**Dilip Raghavan**.*A bound for the weak covering number of the density 0 ideal*.

We prove a ZFC bound for cov^{*}(Z_{0}) where Z_{0}is the ideal of sets of asymptotic density 0. This answers a question about diagonalizing F_{σδ}ideals without adding unbounded reals.

This is joint work with Saharon Shelah.

- 18/03/2015, 17:00 hrs, Week 9, S17#05-11.

**Ng Keng Meng**.*Degrees of categoricity*.

We discuss lowness for isomorphism and degrees of categoricity, and investigate these concepts in equivalence and injection structures. We also discuss the intriguing question of whether every 3-c.e. degree is a degree of categoricity.

- 25/03/2015, 17:00 hrs, Week 10, S17#05-11.

**Frank Stephan**.*Automatic Structures - recent results and open questions*.

Automatic structures are a way to represent algebraic structures using finite automata; all the algebraic operations and relations have to be recognised / verified by finite automata which read the inputs and outputs with the same speed (one symbol per cycle). The talk gives an overview on what structures can be represented this way and which questions are left open in the field.

A paper is available.

- 01/04/2015 - 15/04/2015.

No talks, there is a programme at the IMS about Sets and Computations.

- 10/06/2015, 17:00 hrs, S17#04-04.

**Sheung-Hung Poon**.*On Unfolding Trees of Small Diameters*.

Graph reconfiguration problems have wide applications in contexts including robotics, molecular conformation, animation, wire bending, rigidity and knot theory. The motivation for reconfiguration problems of lattice graphs arises in applications in molecular biology and robotics. We consider the problems of straightening polygonal trees by continuous motions such that rigid edges can rotate around vertex joints and no edge crossings are allowed. A tree can be straightened if all its edges can be aligned along a common straight line such that each edge points "away" from a designated leaf node. In this talk, we start with presenting examples of locked trees in 2D and 3D, respectively. Then we present "minimal" locked trees in 2D, which we discovered recently. Furthermore, we give algorithms to unfold several special classes of diameter-4 trees in 2D. Several interesting questions remain open. For instances, is there a polynomial-time algorithm to determine whether a diameter-4 tree in 2D can be straightened? Can an equilateral tree of diameter 4 in 3D always be straightened?