Tutorials (3h)
Bernard Chazelle
Princeton University, USATitle: Collective Behavior Via Network-Based Dynamics
Abstract: Living systems are often modeled as dynamical systems that enable the emergence of collective behavior from the distributed application of local rules in dynamic networks. This approach raises two issues: How realistic are the models? Can their analyses go beyond numerical simulation? This talk will focus on the second question and provide a short tutorial on a set of novel analytical techniques that have been applied to opinion dynamics, synchronization, swarming, and social learning. This two-part tutorial will assume no prior knowledge on the subject.
Mikolaj Bojanczyk
University of Warsaw, PolandTitle: Languages recognised by finite algebras
Abstract: Regular languages are typically described using automata or regular expressions. There are two important alternatives: logic (regular languages are exactly those languages that can be described using formulas of monadic second-order logic) and algebra (regular languages are exactly those languages that can be recognised by homomorphisms into finite monoids). In my tutorial, I will talk about these two alternatives and their interplay. I will be especially interested in how both logic and algebra can be extended from finite words to other settings, like various kinds of infinite words, or trees or graphs. I will also try to seek common themes among these other settings, and phrase those themes using the language of monads.
Invited Talks (1h)
Natasha Alechina
University of Nottingham , UKTitle: Verifying Systems of Resource-Bounded Agents
Abstract: Approaches to the verification of multi-agent systems are typically based on games or transition systems defined in terms of states and actions. However such approaches often ignore a key aspect of multi-agent systems, namely that the agents’ actions require (and sometimes produce) resources. We briefly survey previous work on the verification of multi-agent systems that takes resources into account, and outline some key challenges for future work. This is joint work with Brian Logan.
Vasco Brattka
Universität der Bundeswehr München, GermanyTitle: Computability and Analysis, a Historical Approach
Abstract: The history of computability theory and and the history of analysis are surprisingly intertwined since the beginning of the twentieth century. For one, E ́mile Borel discussed his ideas on computable real number functions in his introduction to measure theory. On the other hand, Alan Turing had computable real numbers in mind when he introduced his now famous machine model. Here we want to focus on a particular aspect of computability and analysis, namely on computability properties of theorems from analysis. This is a topic that emerged already in early work of Turing, Specker and other pioneers of computable analysis and eventually leads us to the very recent project of classifying the computational content of theorems in the Weihrauch lattice.
Barry Cooper
University of Leeds, UKThe sad news of Barry Cooper's passing has reached us. This talk will be replaced by a Special Session in Barry Cooper's memory. This special Session will be chaired by Mariya Soskova, of Sofia University, Bulgaria.
Delaram Kahrobaei
The City University of New York, USATitle: Algorithmic problems in group theory, their complexity and applications to information security
Abstract: In this talk I will survey some of the algorithmic problems in group theory such as word, conjugacy, subgroup membership, and geodesic length problems. I will speak about their computability and complexity results in a few classes of groups including metabelian groups (joint results with Conchita Martinez- Perez (Spain) and Jonathan Gryak (CUNY)) as well as hyperbolic groups (joint work with Indira Chatterji (France) and Ni Lu (CUNY, GC)). I will survey some cryptosystems that have been proposed using these problems such as non- commutative Diffie-Hellman (a.k.a. Ko-Lee) key exchange as well as cryptosystems using subgroup distortion (joint with I. Chatterji and N. Lu). There are other group structures that have been proposed for cryptography; particularly a key exchange using semidirect products of (semi)groups. This part of my talk is a joint work with Vladimir Shpilrain (City College of New York). We particularly propose free-nilpotent p-groups for this scheme.
Steffen Lempp
University of Wisconsin, USATitle: On Cototality and the Skip Operator in the Enumeration Degrees
Abstract: In the enumeration degrees, we study the notion of cototality (first defined by Pankratov and Solon fifteen years ago (cf. the Pankratov abstract for the 200 Mal’cev meeting as well as Solon’s 2005 and 2006 papers), a notion which has recently been shown to be relevant to other fields like ergodic theory and group theory (cf. Jeandel, in preparation): An enumeration degree is called cototal if it contains a set A with A ≤e A. We present several more examples of naturally occurring cototal sets and separate cototality from a number of related notions, like totality, weak cototality and graph totality. Closely related to this investigation is the notion of the skip operator, which we define by letting A♦ = \overline{KA} where KA ={e|e∈Φe(A)}. The skip is a weak version of the jump Je(A); indeed Je(A) ≡_e KA ⊕ KA ≡_e A ⊕ A♦, but A < e Je(A), whereas in general we only have A♦ \not <=e A. We will present a skip inversion theorem and a number of results that the skip operator can exhibit some bizarre behavior. This is joint work with Andrews, Ganchev, Kuyper, J. Miller, A. Soskova and M. Soskova.
André Nies
University of Auckland, New ZealandTitle: Lowness, Randomness, and computable analysis
Abstract: A lowness notion provides a sense in which an oracle set is close to computable. For instance, being computably dominated (each function computed by A is dominated by a computable function) is a lowness notion; so is that the halting problem relative to A has the least possible Turing complexity. Lowness notions have been studied for at least 50 years. More recently, and perhaps suprisingly, randomness has been applied to investigate lowness notions. For instance, K-triviality of a set of natural numbers (i.e., being far from random in a specific sense) coincides with lowness for Martin-Löf randomness, and many other notions.
Analysis allows us to re-interpret many existing randomness notions originally defined in terms of algorithmic tests. For instance, a real is computably random iff every nondecreasing computable function is differentiable at z, as shown by Brattka, Miller and Nies.
Concepts from analysis have also entered the interaction between lowness and randomness. The Lebesgue density theorem for effectively closed sets provides two randomness notions for a set Z of natural numbers which are slightly stronger than Martin-Löf's. (In the strong form the density of any C containing Z needs to be 1 at Z; in the weak form, it is merely positive.) These two notions have been used to obtain a Turing incomplete Martin-Löf-random above all the K-trivials, thereby solving the so-called covering problem.
In current research, concepts inspired by analysis are used to stratify lowness notions. Cost functions describe a dense hierarchy of subideals of the K-trivial Turing degrees. The Gamma-parameter of a Turing degree is a real number measuring its complexity in terms of the asymptotic density of bit sequences.
The talk will be introductory.
Dominique Perrin
Université Paris-Est Marne-la-Vallée, FranceTitle: Minimal subshifts, Schu ̈tzenberger groups and profinite semigroups
Abstract: Almeida and Costa have shown how one can associate to a minimal subshift X on an alphabet A a J -class J in the free profinite semigroup on A. They have shown that if X is a tree set, the Schützenberger group of J is isomorphic to the free group F(A) on A. We relate their result with results obtained by Berthé, De Felice, Dolce, Leroy, Reutenauer and myself concerning the intersection of the set of factors of S with a subgroup of finite index of F (A).
Reed Solomon
University of Connecticut, USATitle: Stability in reverse mathematics and computable reductions
Abstract: In reverse mathematics, it is often useful to separate combinatorial principles into stable and cohesive versions. We will discuss examples of this phenomena and present recent work on several stable combinatorial principles from the point of view of Weihrauch and computable reducibility. The main results are joint work with Eric Astor, Damir Dzhafarov, Ludovic Patey, Jacob Suggs and Linda Brown Westrick.