Date/Time : 13 Aug 2025 17:00
Venue : S17 #05-11 (Seminar Room 5)
Speaker : Kenny Gill, La Salle University

A countable structure S is indivisible if it satisfies a pigeonhole principle: for any bounded coloring of any presentation of S, there is a monochromatic induced substructure isomorphic to S. This naturally gives rise to an instance-solution problem Ind(S) which outputs such a substructure given a presentation and coloring. We seek to understand both (1) the computational difficulty of solving Ind(S) for various specific S; and (2) how properties of S can translate to properties of Ind(S) and vice versa. This talk will survey what is known about both (1) and (2), highlighting some of the many open problems in the area. In particular, we propose several notions of uniform embeddability of one structure in another which allow one to obtain desirable properties of Ind(S) for large classes of S. This is in part ongoing joint work with Damir Dzhafarov and Reed Solomon.

Add to calendar :

Date/Time : 16 Apr 2025 17:00
Venue : S17 #04-04 (SR3)
Speaker : Isabella Scott,

Ziegler-reducibility (written ≤*) was introduced by Martin Ziegler in his investigations into finitely generated subgroups of existentially closed (e.c.) groups. It is a refinement of both enumeration- and Turing-reducibility and agrees with Q-reducibility on the c.e. sets. Remarkably, Ziegler showed that it can be characterised purely algebraically: for finitely generated G and H, W(H) ≤* W(G) if and only if H embeds in every e.c. group containing G.

In this talk, I shall discuss the connections between computability theory and existentially closed groups, and recent work on the structure of the Ziegler degrees. In particular, we show that there is a minimal Ziegler degree, and, generalising this construction, that the 3-quantifier theory of the Ziegler degrees is undecidable.

This is joint work with Steffen Lempp and Josiah Jacobsen-Grocott.

Add to calendar :

Date/Time : 09 Apr 2025 17:00
Venue : S17 #04-04 (SR3)
Speaker : Frank Stephan, National University of Singapore

For an unfriendly partition, one colours the nodes of a graph using k colours (mostly, k in {2,3}) such that for each two distinct colours a,b and each node of colour a, this node has more neighbours of colour b than of colour a. If one requires “strictly more” then the colouring is called “strictly
unfriendly” and if one requires “more or at least as many” then the colouring is just called “unfriendly”. The sets of the the nodes of each colour form then a partition of the graph. For two colours, one knows that every finite graph has an unfriendly partition while for countable graphs this is an open problem and for uncountable graphs, this is false, as shown by Shelah and Milner [1990]. Joint work with Belanger, Cipriani, Goh, Richter
and Tang shows that for certain recursive graphs, constructing an unfriendly colouring with two colours cannot be solved by any hyperarithmetic oracle, though a more complicated colouring still exists. Thus one cannot expect to find an easy algorithm solving the task and this might be one of the reasons that the problem is still open. Haynes, Hedetniemi and Vasylieva [2015] showed that for two colours, even finite graphs might fail to have a strictly unfriendly colouring. Indeed, it is shown that constructing strictly unfriendly colourings for two or three colours on finite graphs requires, under the Exponential Time Hypothesis, exponential time. Furthermore, one can reduce the problem 3occur3SAT with n variables to the problem of finding an unfriendly colouring of a finite graph with n’ nodes such that the lower bound c^n for 3occur3SAT translates into the lower bound (c^2/11)^n’. These constant c is not explicitly known, but under the assumption ETH it is strictly between 1 and 2. If one only considers graphs of bounded degree, also nontrivial bounds on the runtime can be obtained. Similar results are obtained for three colours. This is joint work with Sanjay Jain and Haoyun Tang. Furthermore, the three authors joint with Ong Weng Qi investigated the complexity of finding unfriendly colourings for two or three colours when for some nodes some colours are preassigned. This was known to be NP-hard, but the finegrained complexity was not studied before.

Add to calendar :

Date/Time : 02 Apr 2025 17:00
Venue : S17 #04-04 (SR3)
Speaker : Jia Zekun,

Post’s problem is one of the most fundamental questions in the early development of recursion theory. In 1944, Post proved the existence of a non-recursive m-incomplete r.e. set and generalized his result to tt-reducibility and Q-reducibility. However, it seemed hopeless to further extend Post’s technique to T-reducibility, and this problem remained open for a decade until it was solved in the affirmative by Friedberg and Muchnik independently. Surprisingly, Post’s method was revived from a series of works by Malcev, Ershov, Marchenkov and Degtev in the 1970s. By introducing an underlying r.e. equivalence relation eta over the natural numbers, they showed that Post’s problem could indeed be solved in Post’s way. A key concept in the proof is the so-called eta-maximal set, resembling Post’s idea of a maximal set. Although Chong and Yang proved that the existence of a maximal set is equivalent to ISigma_2 over PA- + BSigma_2, Downey conjectured that the existence of an eta-maximal set may be simpler despite their similarities in definition. In this talk, we will improve Degtev’s construction of an eta-maximal set and show that Downey is right: PA- + ISigma_1 is enough to carry out and verify the construction.

Add to calendar :

Date/Time : 26 Mar 2025 17:00
Venue : S17 #04-04 (SR3)
Speaker : Chong Chi Tat, National University of Singapore

Combinatorial principles is a prominent area of investigation in reverse mathematics.

The computational complexity of a solution of an instance of a principle began with Jockusch work (1972) on Ramsey’s theorem over the standard model of Peano arithmetic. In general, every instance of a combinatorial principle has a definable solution over the standard model.

For an arbitrary model of RCA_0, however, the situation is not clear. There exist weak models and instances of combinatorial principles (such as Ramsey’s theorem for pairs) for which no definable solution is known. In this talk we present an analysis of the problem of definable solutions and some nonexistence results.

Add to calendar :

Date/Time : 05 Mar 2025 17:00
Venue : S17 #04-04 (SR3)
Speaker : Subin Pulari, LaBRI

Measuring the informational content of real numbers has been a significant area of inquiry in algorithmic information theory. Finite-state compressibility (or finite-state dimension) of a real number is a value in [0, 1] which quantifies the amount of information/randomness in the real number as measured using finite-state automata. Finite-state dimension is the lower asymptotic ratio of compression achievable on an infinite string using information-lossless finite-state compressors. Interestingly, the finite-state dimension of a real number is also equal to the block Shannon entropy rate of the infinite sequence representing the expansion of the real number in a base b. A line of work, originating from Schnorr and Stimm (1972), has established that a number is Borel normal in base b if and only if its base b expansion has finite-state compressibility equal to 1, i.e., is incompressible. Hence, normal numbers are precisely the class of numbers that are incompressible using finite-state compressors.

Most of the prior research on finite-state dimension has relied on combinatorial methods. In this talk we explore how tools from Fourier analysis can be employed to gain new insights into the compressibility of real numbers by solving an open question posed by Lutz and Mayordomo regarding the existence of absolutely dimensioned numbers.

Absolutely normal numbers, being finite-state incompressible in every base of expansion, are precisely those numbers which have finite-state dimension equal to 1 in every base. At the other extreme, for example, every rational number has 0 finite-state dimension in every base. Generalizing this, Lutz and Mayordomo asked the following question: Does there exist any s strictly between 0 and 1 and a real number r such that r has finite state dimension equal to s in every base?. In this talk we use several tools involving exponential sums and techniques from Schmidt’s work in 1960 to construct, for any given s in (0,1], a real number r having finite-state compressibility equal to s in every base.

We also discuss further applications of exponential sums in analyzing and characterizing the finite-state compressibility of real numbers.

Add to calendar :

Date/Time : 19 Feb 2025 17:00
Venue : S17 #04-04 (SR3)
Speaker : Makoto Tatsuta, National Institute of Informatics

Separation logic is successful for software verification of heap-manipulating programs. Numbers are necessary to be added to separation logic for verification of practical software where numbers are important. However, properties of the validity such as decidability and complexity for separation logic with numbers have not been fully studied yet. This paper presents the translation of Pi-0-1 formulas in Peano arithmetic to formulas in a small fragment of separation logic with numbers, which consists only of the intuitionistic points-to predicate, 0 and the successor function.
Then this paper proves that a formula in Peano arithmetic is valid in the standard model if and only if its translation in this fragment is valid in the standard interpretation. As a corollary, this paper also gives a perspective proof for the undecidability of the validity in this fragment. Since Pi-0-1 formulas can describe consistency of logical systems and non-termination of computations, this result also shows that these properties discussed in Peano arithmetic can also be discussed in such a small fragment of separation logic with numbers.

Add to calendar :

Date/Time : 05 Feb 2025 17:00
Venue : S17 #04-04 (SR3)
Speaker : Frank Stephan, National University of Singapore

The talk presents joint work with David Belanger (Singapore), C.T.~Chong (Singapore), Rupert Hoelzl (Munich), Gordon Hoi (Singapore), Sanjay Jain (Singapore), Dilip Raghavan (Singapore), Frank Stephan (Singapore), Daniel Turetsky (Wellington) and Jing Zhang (Toronto) published in four papers. The first one dealt with comparing the growth behaviour of functions or families of functions partial-recursive relative to an oracle and classified oracles with respect to this measure. The second, third and fourth papers are about reverse mathematics and study weakly represented families, that are families of functions computed relative to some oracle in the second order part of the model (all functions in the family use the same oracle). These families are used as a tool to define notions like dominated (every weakly represented family is dominated by some function in the model), hyperimmune, biimmune and so on. Furthermore, one can such families also use as a hypothesis space for classes to be learnt – this extends the study to inductive inference. This is a survey talk with sample proofs.

Add to calendar :

Date/Time : 18 Dec 2024 17:00
Venue : S17 #05-11 (SR5)
Speaker : Manlio Valenti, Swansea University

Recall that, in a partial order P, b is a minimal cover of b if the interval (a,b) is empty. A strengthening of this notion is the one of strong minimal cover, namely b is a strong minimal cover of a if c<b implies c\le a. In this talk, we provide a complete characterization of how minimal covers and strong minimal covers in the Weihrauch degrees look like. As a consequence, we obtain that the Weihrauch degree of the identity problem id can be defined as the highest top of a strong minimal cover, or the least degree whose upper cone is dense. In other words, “being (uniformly) computable” is a first-order definable property in (W,<). This implies that the first-order theory of the Weihrauch degrees (below id) is recursively isomorphic to the third-order theory of true arithmetic.

This is joint work with Steffen Lempp, Joe Miller, Arno Pauly, and Mariya Soskova.

Add to calendar :