Pursuit of the Universal

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.

We focus in this survey on effectiveness issues for S-adic subshifts and tilings. An S-adic subshift or tiling space is a dynamical system obtained by iterating an infinite composition of substitutions, where a substitution is a rule that replaces a letter by a word (that might be multi-dimensional), or a tile by a finite union of tiles. Several notions of effectiveness exist concerning S-adic subshifts and tiling spaces, such as the computability of the sequence of iterated substitutions, or the effectiveness of the language. We compare these notions and discuss effectiveness issues concerning classical properties of the associated subshifts and tiling spaces, such as the computability of shift-invariant measures and the existence of local rules (soficity). We also focus on planar tilings.

Mathematical modeling and computational analyses of biological systems generally pose to modelers questions like: “Which modeling approach is suitable to describe the system we are interested in? Which computational tools do we need to simulate and analyze this system? What kind of predictions the model is expected to give?”. To answer these questions, some general tips are here suggested to choose the proper modeling approach according to the size of the system, the desired level of detail for the system description, the availability of experimental data and the computational costs of the analyses that the model will require. The attention is then focused on the numerous advantages of reaction-based modeling, such as its high level of detail and easy understandability, or the possibility to run both deterministic and stochastic simulations exploiting the same model. Some notes on the computational methods required to analyze reaction-based models, as well as their parallelization on Graphics Processing Units, are finally provided.

Molecular evolutionary methods and tools are difficult to validate as we have almost no direct access to ancient molecules. Inference methods may be tested with simulated data, producing full scenarios they can be compared with. But often simulations design is concomitant with the design of a particular method, developed by a same team, based on the same assumptions, when both should be blind to each other. In silico experimental evolution consists in evolving digital organisms with the aim of testing or discovering complex evolutionary processes. Models were not designed with a particular inference method in mind, only with basic biological principles. As such they provide a unique opportunity to blind test the behavior of inference methods. We give a proof of this concept on a comparative genomics problem: inferring the number of inversions separating two genomes. We use Aevol, an in silico experimental evolution platform, to produce benchmarks, and show that most combinatorial or statistical estimators of the number of inversions fail on this dataset while they were behaving perfectly on ad-hoc simulations. We argue that biological data is probably closer to the difficult situation.

The history of computability theory and the history of analysis are surprisingly intertwined since the beginning of the twentieth century. For one, Émil 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.

We revisit the investigation of the computational content of the Brouwer Fixed Point Theorem in [7], and answer the two open questions from that work. First, we show that the computational hardness is independent of the dimension, as long as it is greater than 1 (in [7] this was only established for dimension greater than 2). Second, we show that restricting the Brouwer Fixed Point Theorem to L-Lipschitz functions for any $$L > 1$$L>1 also does not change the computational strength, which together with prior results establishes a trichotomy for $$L > 1$$L>1, $$L = 1$$L=1 and $$L < 1$$L<1.

Secret sharing concerns the distribution of some secret information among a number of parties and is among the most well known tools in cryptography. Secret sharing schemes with certain additional algebraic properties, known as linearity and multiplicativity, have important applications in the area of secure multiparty computation and other areas such as zero knowledge proofs. Secret sharing also has a strong relationship with coding theory and motivates new problems in that field. I will survey several of the recent results in the area and some of their applications.

This note explores an often overlooked question about the characterization of the notion model of computation which was originally identified by Cobham [5]. A simple formulation is as follows: what primitive operations are allowable in the definition of a model such that its time and space complexity measures provide accurate gauges of practical computational difficulty? After exploring the significance of this question in the context of subsequent work on machine models and simulations, an adaptation of Kreisel’s squeezing argument [17] for Church’s Thesis involving Gandy machines [11] is sketched which potentially bears on this question.

A secret sharing scheme is non-perfect if some subsets of players that cannot recover the secret have partial information about it. This paper is a survey of the recent advances in non-perfect secret sharing schemes. We provide an overview of the techniques for constructing efficient non-perfect secret sharing schemes, bounds on the efficiency of these schemes, and results on the characterization of the ideal ones. We put special emphasis on the connections between non-perfect secret sharing schemes and polymatroids, matroids, information theory, and coding theory.

Borwein and Ditor (Canadian Math. Bulletin 21 (4), 497–498, 1978) proved the following. Let $$\mathcal {A}\subset {\mathbb {R}}$$A⊂R be a measurable set of positive measure and let $${\left\langle {r_m}\right\rangle }_{m\in \omega }$$rmm∈ω be a null sequence of real numbers. For almost all $$z \in \mathcal {A}$$z∈A, there is m such that $$z+r_m\in \mathcal {A}$$z+rm∈A.In this note we mainly consider the case that $$\mathcal {A} $$A is $$\varPi ^0_{1}$$Π10 and the null sequence $${\left\langle {r_m}\right\rangle }_{m\in \omega }$$rmm∈ω is computable. We show that in this case every Oberwolfach random real $$z \in \mathcal {A}$$z∈A satisfies the conclusion of the theorem. We extend the result to finitely many null sequences. The conclusion is now that for almost every $$z \in \mathcal {A}$$z∈A, the same m works for each null sequence.We indicate how this result could separate Oberwolfach randomness from density randomness.

Recently we have defined Staircase-Generator codes (St-Gen codes) and their variant with a random split of the generator matrix of the codes. One unique property of these codes is that they work with arbitrary error sets. In this paper we analyze the semantic security against chosen plaintext attack (IND-CPA) and key-privacy i.e. indistinguishability of public keys under chosen plaintext attack (IK-CPA) of the encryption scheme with random split of St-Gen codes. In a similar manner as it was done by Nojima et al. and later by Yamakawa et al. we show that padding the plaintext with a random bit-string provides IND-CPA and IK-CPA in the standard model. The difference with McEliece scheme is that with our scheme the length of the padded random string is significantly shorter.

Baire Category is an important concept in mathematical analysis. It gives a notion of large set, hence a way of identifying the properties of typical objects. One of the most important applications of Baire Category is to provide a way of proving the existence of objects with specified properties without having to give an explicit construction, showing at the same time that these properties are prevalent. For instance it has been extensively used in mathematical analysis to better understand and separate classes of real functions such as analytic and smooth functions (see [9] for a wide range of applications of the Baire Category Theorem in analysis).

We give an overview of the interplay between computability and symbolic dynamics.

In this survey, we describe a general key exchange protocol based on semidirect product of (semi)groups (more specifically, on extensions of (semi)groups by automorphisms), and then focus on practical instances of this general idea. This protocol can be based on any group or semigroup, in particular on any non-commutative group. One of its special cases is the standard Diffie-Hellman protocol, which is based on a cyclic group. However, when this protocol is used with a non-commutative (semi)group, it acquires several useful features that make it compare favorably to the Diffie-Hellman protocol. The focus then shifts to selecting an optimal platform (semi)group, in terms of security and efficiency. We show, in particular, that one can get a variety of new security assumptions by varying an automorphism used for a (semi)group extension.

Pour-El and Richards [PER89], Weihrauch [Weih00], and others have extended Recursive Analysis from real numbers and continuous functions to rather general topological spaces. This has enabled and spurred a series of rigorous investigations on the computability of partial differential equations in appropriate advanced spaces of functions. In order to quantitatively refine such qualitative results with respect to computational efficiency we devise, explore, and compare natural encodings (representations) of compact metric spaces: both as infinite binary sequences (TTE) and more generally as families of Boolean functions via oracle access as introduced by Kawamura and Cook ([KaCo10], Sect. 3.4). Our guide is relativization: Permitting arbitrary oracles on continuous universes reduces computability to topology and computational complexity to metric entropy in the sense of Kolmogorov. This yields a criterion and generic construction of optimal representations in particular of (subsets of) $$L^p$$ Lp and Sobolev spaces that solutions of partial differential equations naturally live in.

When perturbating a cellular automaton by a random noise (positive probability of error, for each cell independently), the system is generally expected to be ergodic, meaning that during its evolution, it eventually forgets about its initial condition. For a high noise, this can be shown by coupling. However, for a small noise, ergodicity is often very difficult to prove. We present extensions of the coupling method to small noises when the cellular automaton has some specific properties (hardcore exclusion, nilpotency, permutivity).

The notion of type to designate a class of values, and the operations on those values, is a central feature of any modern programming language. In fact, we keep calling them programming languages, but the part of a modern language devoted to the actual specification of the control flow (that is, programming stricto sensu) is only a fraction of the language itself, and two different languages are not much apart under that perspective. What “makes a language” are much more its modelling capabilities to describe complex relations between portions of code and between data. In a word, the central part of a language is made by the abstraction mechanisms it provides to model its application domain(s), all issues the language theorist may well group together in the type chapter of a language definition.

Founded in 1957, the Association Française de Calcul (AFCAL) was the first French society dedicated mainly to numerical computation. Its rapid growth and amalgamation with sister societies in related fields (Operations Research, Automatic Control) in the 1960s resulted in changes of its name and purpose, including the invention and adoption of the term informatique in 1962–1964, then in the adoption of cybernétique in 1967. Our paper aims at explicating the motives of its creation, its evolving definition and the functions it fulfilled. We seek to understand how this association, altogether a learned and a professional society, contributed to the emergence and recognition of Computing as an academic discipline in France. The main sources are the scattered surviving records of AFCAL, conserved in the archives of the Observatoire de Paris, of the Institut de Mathématiques appliquées de Grenoble (IMAG) and of the CNRS’ Institut Blaise Pascal in Paris, as well as AFCAL’s first congress and journal, Chiffres.

Recent work in reverse mathematics on combinatorial principles below Ramsey’s theorem for pairs has made use of a variety of computable reductions to give a finer analysis of the relationships between these principles. We use three concrete examples to illustrate this work, survey the known results and give new negative results concerning $$\mathsf {RT}^1_k$$RTk1, $$\mathsf {SRT}^2_\ell $$SRTℓ2 and $$\mathsf {COH}$$COH. Motivated by these examples, we introduce several variations of $$\mathsf {ADS}$$ADS and describe the relationships between these principles under Weihrauch and strong Weihrauch reductions.

The idea to find the “maximal number that can be named” can be traced back to Archimedes (see his Psammit [1]). From the viewpoint of computation theory the natural question is “which number can be described by at most n bits”? This question led to the definition of the so-called “busy beaver” numbers (introduced by T. Rado). In this note we consider different versions of the busy beaver-like notions defined in terms of Kolmogorov complexity. We show that these versions differ depending on the version of complexity used (plain, prefix, or a priori complexities) and find out how these notions are related, providing matching lower and upper bounds.

We define the domino problem for tilings over self-similar structures of $$\mathbb {Z}^d$$Zd given by forbidden patterns. In this setting we exhibit non-trivial families of subsets with decidable and undecidable domino problem.

We propose a formalization of generic algorithms that includes analog algorithms. This is achieved by reformulating and extending the framework of abstract state machines to include continuous-time models of computation. We prove that every hybrid algorithm satisfying some reasonable postulates may be expressed precisely by a program in a simple and expressive language.

We introduce two notions of effective reducibility for set-theoretical statements, based on computability with Ordinal Turing Machines (OTMs), one of which resembles Turing reducibility while the other is modelled after Weihrauch reducibility. We give sample applications by showing that certain (algebraic) constructions are not effective in the OTM-sense and considering the effective equivalence of various versions of the axiom of choice.

Let $$\mathcal {A} \subseteq {}^\omega {2}$$A⊆ω2 be measurable. The density set $$D \mathcal {A}$$DA is the set of $$Z \in {}^\omega {2}$$Z∈ω2 such that the local measure of $$\mathcal {A}$$A along Z tends to 1. Suppose that $$\mathcal {A}$$A is a $$\varPi ^0_{1}$$Π10 set with empty interior and the uniform measure of $$\mathcal {A}$$A is a positive computable real. We show that $$D \mathcal {A}$$DA is lightface $$\varPi ^0_3$$Π30 complete for effective Wadge reductions. This is an algorithmic version of a result in descriptive set theory by Andretta and Camerlo [1]. They show a completeness result for boldface $$\varPi ^0_3$$Π30 sets under plain Wadge reductions.

A general correction grammar for a language L is a program g that, for each $$(x,t)\in \mathbb {N} ^2$$(x,t)∈N2, issues a yes or no (where when $$t=0$$t=0, the answer is always no) which is g’s t-th approximation in answering “$$x{\in } L?$$x∈L?”; moreover, g’s sequence of approximations for a given x is required to converge after finitely many mind-changes. The set of correction grammars can be transfinitely stratified based on O, Kleene’s system of notation for constructive ordinals. For $$u\in O$$u∈O, a u-correction grammar’s mind changes have to fit a count-down process from ordinal notation u; these u-correction grammars capture precisely the $$\varSigma _u^{-1}$$Σu-1 sets in Ershov’s hierarchy of sets for $$\varDelta _2^0$$Δ20. Herein we study the relative succinctness between these classes of correction grammars. Example: Given u and v, transfinite elements of O with $$u<_ov$$u<ov (Kleene’s ordering on O), for each $$\emptyset ^{(2)}$$∅(2)-computable $$H:\mathbb {N} \rightarrow \mathbb {N} $$H:N→N, there is a v-correction grammar $$i_v$$iv for a finite (alternatively, a co-finite) set A such that the smallest u-correction grammar for A is $${>}H({i_{v}})$$>H(iv). We also exhibit relative succinctness progressions in these systems of grammars and study the “information-theoretic” underpinnings of relative succinctness. Along the way, we verify and improve slightly a 1972 conjecture of Meyer and Bagchi.

For a Turing degree $$\mathbf {x}$$x, we investigate the automorphisms of the lattice of $$\mathbf {x}$$x-c.e. vector spaces. We establish the equivalence of the embedding relation for these automorphism groups with the order relation on the corresponding Turing degrees. By a result of Guichard the automorphisms of the lattice of $$\mathbf {x}$$x-c.e. vector spaces are induced by $$\mathbf {x}$$x-computable invertible semilinear transformations, GSL$$_{\mathbf {x}}$$x. We prove that the Turing degree spectrum of the group GSL$$_{\mathbf {x}}$$x is the upper cone of Turing degrees $$\ge \mathbf {x}^{\prime \prime }$$≥x″.

The quest for colorful components (connected components where each color is associated with at most one vertex) inside a vertex-colored graph has been widely considered in the last ten years. Here we consider two variants, Minimum Colorful Components (MCC) and Maximum Edges in transitive Closure (MEC), introduced in the context of orthology gene identification in bioinformatics. The input of both MCC and MEC is a vertex-colored graph. MCC asks for the removal of a subset of edges, so that the resulting graph is partitioned in the minimum number of colorful connected components; MEC asks for the removal of a subset of edges, so that the resulting graph is partitioned in colorful connected components and the number of edges in the transitive closure of such a graph is maximized. We study the parameterized and approximation complexity of MCC and MEC, for general and restricted instances.

Let $$\kappa $$κ be an uncountable cardinal with $$\kappa ^{<\kappa }=\kappa $$κ<κ=κ. In this paper we introduce $${{\mathrm{\mathbb {R}}}}_\kappa $$Rκ, a Cauchy-complete real closed field of cardinality $$2^\kappa $$2κ. We will prove that $${{\mathrm{\mathbb {R}}}}_\kappa $$Rκ shares many features with $${{\mathrm{\mathbb {R}}}}$$R which have a key role in real analysis and computable analysis. In particular, we will prove that the Intermediate Value Theorem holds for a non-trivial subclass of continuous functions over $${{\mathrm{\mathbb {R}}}}_\kappa $$Rκ. We propose $${{\mathrm{\mathbb {R}}}}_\kappa $$Rκ as a candidate for extending computable analysis to generalised Baire spaces.

The present work shows that Cayley automatic groups are semiautomatic and exhibits some further constructions of semiautomatic groups and in particular shows that every finitely generated group of nilpotency class 3 is semiautomatic.

We characterize up to isomorphism the Boolean algebra (BA, for short) of regular piecewise testable languages and show the decidability of classes of regular languages related to this characterization. This BA turns out isomorphic to several other natural BAs of regular languages, in particular to the BA of regular aperiodic languages.

We show that for many natural computable metric spaces and computable domains the first order theory of the lattice of effectively open sets is hereditarily undecidable. Moreover, for several important spaces (e.g., finite-dimensional Euclidean spaces and the domain $$P\omega $$Pω) this theory is m-equivalent to the first-order arithmetic.

The model of interactive Turing machines (ITMs) has been proposed to characterise which stream translations are interactively computable; the model of reactive Turing machines (RTMs) has been proposed to characterise which behaviours are reactively executable. In this article we provide a comparison of the two models. We show, on the one hand, that the behaviour exhibited by ITMs is reactively executable, and, on the other hand, that the stream translations naturally associated with RTMs are interactively computable. We conclude from these results that the theory of reactive executability subsumes the theory of interactive computability. Inspired by the existing model of ITMs with advice, which provides a model of evolving computation, we also consider RTMs with advice and we establish that a facility of advice considerably upgrades the behavioural expressiveness of RTMs: every countable transition system can be simulated by some RTM with advice up to a fine notion of behavioural equivalence.

We study interactions between Skolem Arithmetic and certain classes of Circuit Satisfiability and Constraint Satisfaction Problems (CSPs). We revisit results of Glaßer et al. [16] in the context of CSPs and settle the major open question from that paper, finding a certain satisfiability problem on circuits—involving complement, intersection, union and multiplication—to be decidable. This we prove using the decidability of Skolem Arithmetic. Then we solve a second question left open in [16] by proving a tight upper bound for the similar circuit satisfiability problem involving just intersection, union and multiplication. We continue by studying first-order expansions of Skolem Arithmetic without constants, $$(\mathbb {N};\times )$$(N;×), as CSPs. We find already here a rich landscape of problems with non-trivial instances that are in P as well as those that are NP-complete.

An equality language is a relational structure with infinite domain whose relations are first-order definable in equality. We classify the extensions of the quantified constraint satisfaction problem over equality languages in which the native existential and universal quantifiers are augmented by some subset of counting quantifiers. In doing this, we find ourselves in various worlds in which dichotomies or trichotomies subsist.

For a ring R, Hilbert’s Tenth Problem HTP(R) is the set of polynomial equations over R, in several variables, with solutions in R. We consider computability of this set for subrings R of the rationals. Applying Baire category theory to these subrings, which naturally form a topological space, relates their sets HTP(R) to the set HTP$$(\mathbb {Q})$$(Q), whose decidability remains an open question. The main result is that, for an arbitrary set C, HTP$$(\mathbb {Q})$$(Q) computes C if and only if the subrings R for which HTP(R) computes C form a nonmeager class. Similar results hold for 1-reducibility, for admitting a Diophantine model of $$\mathbb {Z}$$Z, and for existential definability of $$\mathbb {Z}$$Z.

We identify computability-theoretic properties enabling us to separate various statements about partial orders in reverse mathematics. We obtain simpler proofs of existing separations, and deduce new compound ones. This work is part of a larger program of unification of the separation proofs of various Ramsey-type theorems in reverse mathematics in order to obtain a better understanding of the combinatorics of Ramsey’s theorem and its consequences. We also answer a question of Murakami, Yamazaki and Yokoyama about pseudo Ramsey’s theorem for pairs.

We present a constructive proof of a Stone-Weierstrass theorem for totally bounded metric spaces ($$\mathrm {\mathbf {SWtbms}}$$SWtbms) which implies Bishop’s Stone-Weierstrass theorem for compact metric spaces ($$\mathrm {\mathbf {BSWcms}}$$BSWcms) found in [3]. Our proof has a clear computational content, in contrast to Bishop’s highly technical proof of $$\mathrm {\mathbf {BSWcms}}$$BSWcms and his hard to motivate concept of a (Bishop-)separating set of uniformly continuous functions. All corollaries of $$\mathrm {\mathbf {BSWcms}}$$BSWcms in [3] are proved directly by $$\mathrm {\mathbf {SWtbms}}$$SWtbms. We work within Bishop’s informal system of constructive mathematics $$\mathrm {BISH}$$BISH.