Monday May 8/23 Alberto Marcone (Università di Udine)
Title: 3 is much larger than 2 in reverse mathematics
Abstract: A partial order is a well-partial order (wpo) if it does not contain infinite descending chains and infinite antichains. In the
1960's Nash-Williams introduced a strengthening of this notion, called better partial order (bpo), which has better closure properties than wpo
and was therefore used to show that many partial orders are wpo.
In this talk we deal with the foundations of bpo theory from the viewpoint of reverse mathematics, a research program in mathematical logic that aims at establishing the weakest axioms needed to prove a statement. From this perspective, even the statement that finite partial orders are bpo is nontrivial. About twenty years ago I showed that "2 is bpo" (where 2 is the antichain with two elements) is provable in RCA0, the base theory of reverse mathematics, and asked about the strength of "3 is bpo". No progress was made on the question until last year, when Anton Freund showed that "3 is bpo" implies ACA0^+, providing a significant lower bound for the strength of the statement. Although the question is not completely settled yet (the upper bound is the stronger theory ATR0), we can now affirm that 3 is much larger than 2.
Building on this result, in recent work with Freund, Pakhomov and Soldà, we characterized the partial orders that a theory such as ACA0 (which does not prove that 3 is bpo) proves to be bpo.
Monday Dec 5/22 Toni Huynh (Sapienza University)
Title: Strengthening Convex Relaxations of 0/1-Sets Using Boolean Formulas
Abstract: In this talk, we present a novel connection between circuit complexity and integer programming. In convex integer programming, various procedures have been developed to strengthen convex relaxations of sets of integer points.
On the one hand, there exist several general-purpose methods that strengthen relaxations without specific knowledge of the set of feasible integer points, such as popular linear programming or semi-definite programming hierarchies. On the other hand, various methods have been designed for obtaining strengthened relaxations for very specific sets that arise in combinatorial optimization, such as the travelling salesman problem.
We propose a new efficient method that interpolates between these two approaches. Our procedure strengthens any convex set containing a set S of 0/1-points by exploiting certain additional information about S. Namely, the required extra information will be in the form of a Boolean formula F defining the target set S. The new relaxation is obtained by "feeding'' the convex set S into the formula F.
We analyze various aspects regarding the strength of our procedure. As one application, interpreting an iterated application of our procedure as a hierarchy, our findings simplify, improve, and extend previous results by Bienstock and Zuckerberg on covering problems. This is joint work with Samuel Fiorini and Stefan Weltge.
Monday Nov 21/22 - Luca San Mauro (Sapienza University)
Title: Learning families of algebraic structures
Abstract: Algorithmic Learning Theory (ALT), initiated by Gold and Putnam in the 1960s, comprehends several formal frameworks for the inductive inference. Broadly construed, ALT models the ways in which a learner may achieve systematic knowledge about a given environment, by accessing more and more data about it. In classical paradigms, the objects to be inferred are either formal languages or computable functions. In this talk, we present the following framework: An agent receives larger and larger pieces of an arbitrary copy of a countable structure and, at each stage, is required to output a conjecture about the isomorphism type of such a structure. The learning is successful if the conjectures eventually stabilize to a correct guess. We offer a complete model theoretic characterization of which families of structures are learnable. We also discuss a descriptive set theoretic interpretation of our framework, which allows us to define a hierarchy of non-learnability.
This is joint work with Nikolay Bazhenov, Vittorio Cipriani, and Ekaterina Fokina.
Monday Nov 14/22 - Giuseppe Perelli (Sapienza University)
Title: From Synthesis to Rational Synthesis: a Logic-Based Approach for Multi-Agent Systems Verification
Abstract: Synthesis is the problem of programming an intelligent agent and its interaction with the environment in a way that its behaviour is correct by construction, that is, it fulfils a given task no matter how the environment reacts. The solution to this problem can be interpreted as the winning strategy in a suitably defined two-player (formal) game. Rational Synthesis (RS) is a recent evolution of Synthesis, in which the setting is not viewed as an adversarial dispute, but rather as a Multi-Agent System, where each agent has their own specification. In terms of games, RS corresponds to no longer maximizing an individual payoff against all possible environment's behaviours (two-player zero-sum), but rather synthesising a strategy profile that is in some sort of equilibrium, i.e., prevents agents to improve payoff by deviating from it (multi-player nonzero-sum).
I will give an overview to the Synthesis and Rational Synthesis, presenting recent results and developments, and showing how the logic-based approach comes in very handy for representing and solving these problems. Finally, I will outline some current and future direction I am taking within the field.