CiE 2016: Pursuit of the Universal

June 27th 2016 - July 1st 2016, Paris, France

The program committee has invited the following researchers to give plenary talks at CiE 2016.

Tutorials (3h)

Bernard Chazelle

Princeton University, USA

Title: 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, Poland

Title: 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 , UK

Title: 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, Germany

Title: 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, UK

The 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, USA

Title: 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, USA

Title: 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 Zealand

Title: Lowness, Randomness, and computable analysis

Abstract: A lowness notion provides a sense in which an oracle set A 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 z 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 C 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, France

Title: 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, USA

Title: 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.