Archives of: NUS logic seminar

Frank Stephan: Finitely generated semiautomatic groups

Update on the Logic Seminar at the National University of Singapore
(the originally announced speaker is ill and will speak on 12 April 2017)

Date: Wednesday, 22 March 2016, 17:00 hrs

Room: S17#04-05, Department of Mathematics, NUS

Speaker: Frank Stephan

Title: Finitely generated semiautomatic groups

URL: http://www.comp.nus.edu.sg/~fstephan/logicseminar.html

The present work shows that Cayley automatic groups are semiautomatic
and exhibits some further constructions of semiautomatic groups.
Furthermore, the present work establishes that every finitely
generated group of nilpotency class $3$ is semiautomatic.

André Nies: Structure within the class of K-trivial sets

SEMINAR ANNOUNCEMENT

Title: Structure within the class of K-trivial sets

Prof. André Nies
Department of Computer Science
University of Auckland
Date:    6 February 2017 (Monday)
Time:      4.00pm – 5.00pm
Venue:     MAS Executive Classroom 1 #03-06,
School of Physical and Mathematical Sciences  and quantum settings

The K-trivial sets are antirandom in the sense that the initial segment complexity in terms of prefix-free Kolmogorov complexity K grows as slowly as possible. Since 2002, many  alternative characterisations of this class have been found: properties such as low for K, low for Martin-Löf (ML) randomness, and basis for ML randomness, which state in one way or the other that the set is close to computable.

Initially the class looked quite amorphous. More recently, internal structure has been found. Bienvenu et al. (JEMS 2016) showed that there is a “smart” K-trivial set, in the sense that any random oracle computing it computes all K-trivials. Greenberg, Miller and Nies(submitted)  showed that there is a dense hierarchy of subclasses. Even more recent results with Turetsky combine the two approaches using cost functions. ML-reducibility (A is below B if every random oracle computing B also computes A) appears to a good way to compare the complexity of K-trivials, but the vexing question remains whether this reducibility is arithmetical.

Jonathan Verner: A Ramsey Theorem for metric spaces

Invitation to the Logic Seminar at the National University of Singapore

Date: Wednesday, 16 November 2016, 17:00 hrs

Room: S17#04-05, Department of Mathematics, NUS

Speaker: Jonathan Verner

Title: A Ramsey Theorem for metric spaces

Abstract: attached.

Joint Work With Saharon Shelah

URL: http://www.comp.nus.edu.sg/~fstephan/logicseminar.html

David Belanger: An effective perfect-set theorem

Invitation to the Logic Seminar at the National University of Singapore

Date: Wednesday, 9 Nov 2016, 17:00 hrs

Room: S17#04-05, Department of Mathematics, NUS

Speaker: David Belanger

Title: An effective perfect-set theorem

URL: http://www.comp.nus.edu.sg/~fstephan/logicseminar.html

Abstract: We gauge the difficulty of finding a perfect subtree in a tree
of a given Cantor-Bendixson rank. To simplify the analysis we introduce
half-derivative, and extend the definition of rank to include values of
the form n-and-a-half; each increase of one-half in the rank corresponds
to one added jump in the perfect-subtree problem.

Liu Yong: Revisit maximal d.r.e. degrees

Invitation to the Logic Seminar at the National University of Singapore

Date: Friday, 4 November 2016, 13:00 hrs and 14:00 hrs

Room: S17#07-24, Department of Mathematics, NUS

Talk 1 – Speaker: Liu Yong.

Title: Revisit maximal d.r.e. degrees.

Abstract: We will begin with a brief review of maximal d.r.e. construction,
and show that for any cappable r.e. set A, there is a maximal d.r.e. set D,
which computes A. We also show how to build a maximal d.r.e. set D, avoiding
upper cone of two nonrecursive r.e. sets.

Talk 2 – Speaker: Peng Cheng

Title: A brief introduction to the Ershov hierarchy.

Abstract: Ershov generalized the n-r.e. hierarchy to transfinite levels
based on Kleene’s ordinals. It is a natural measure to study the sets below K.
We will survey some early work by Ershov and others on the Ershov hierarchy
and present the most fundamental results. We will also provide some questions
we are thinking now.

URL: http://www.comp.nus.edu.sg/~fstephan/logicseminar.html

Wu Huishan: Avoiding degrees of orders on torsion-free abelian groups

Invitation to the Logic Seminar at the National University of Singapore

Date: Wednesday, 2 November 2016, 17:00 hrs

Room: S17#04-05, Department of Mathematics, NUS

Speaker: Wu Huishan, Nanyang Technological University

Title: Avoiding degrees of orders on torsion-free abelian groups.

URL: http://www.comp.nus.edu.sg/~fstephan/logicseminar.html

An abelian group admits an order iff it is torsion-free,
we consider degrees of orders on computable torsion-free abelian groups.
For a computable torsionfree abelian group G, Solomon (2003) showed
that if G has rank 1, then it has exactly two computable orders;
if G has finite rank 2 or more, then it has orders of all Turing
degrees; and if G has infinite rank, then it has orders of
all degrees greater equal 0′.
Motivated by the question whether the set of all degrees of orders
on a computable torsion-free abelian group is closed upwards,
Kach, Lange and Solomon (2013) constructed a computable
torsion-free abelian group G of infinite rank with exactly
two computable orders and a noncomputable, computably enumerable
set C such that every C-computable order on G
is computable, so this G has no orders in deg(C) > 0,
but has orders in 0, a negative answer is provided for
above question.
One proposed research topic is to study the computational complexity
of above computably enumerable set C from the standpoint of
classical computability theory, we will present a recent work on
this topic from the viewpoint of high/low hierarchy.
This is a joint work with my supervisor Wu Guohua.

Sanjay Jain: Deciding parity games in quasipolynomial time

Invitation to the Logic Seminar at the National University of Singapore

Date: Wednesday, 26 October 2016, 17:00 hrs

Room: S17#04-05, Department of Mathematics, NUS

Speaker: Sanjay Jain

Title: Deciding parity games in quasipolynomial time

URL: http://www.comp.nus.edu.sg/~fstephan/logicseminar.html

Parity games are games on finite graphs where each
node has a value. Two players, Anke and Boris,
move alternately a marker through the graph
and plays between the two players have infinite
duration. One determines the winner of such an infinite
play by taking the largest value of a node which is visited
infinite often; if this value is even then the first player
Anke wins else the second player Boris wins.

An important question is to determine the player who
has a winning strategy in such games. One evaluates such
algorithms in terms of the number n of nodes and number
m of colours and other possible parameters. Prior work
has given algorithms with runtime O(n^{m/3}) and
O(n^{Sqrt(n)}). The talk will present an improved
quasipolynomial algorithm with runtime O(n^{log(m)+8}).
Furthermore, if m < log(n), one can determine the winner
in time O(n^5); thus the problem is fixed-parameter
tractable, bringing it from the prior known complexity
class XP into FPT.

This is joint work with Cristian Calude, Bakhadyr
Khoussainov, Li Wei and Frank Stephan. The paper
is available at

http://www.comp.nus.edu.sg/~sanjay/paritygame.pdf

Reese Johnston: Computability of isolated paths in uncountable binary trees

Invitation to the Logic Seminar at the National University of Singapore

Date: Wednesday, 05 October 2016, 17:00 hrs

Room: S17#04-05, Department of Mathematics, NUS

Speaker: Reese Johnston

Title: Computability of isolated paths in uncountable binary trees.

Abstract: Alpha-recursion theory has been a target of study for some time;
a defining feature is the exotic behavior that can occur for general
ordinals alpha. In this talk, we consider the particular, and
better-behaved, case in which alpha is omega-1, and approach a class of
problems well-studied in the classical case: Pi-0-1-classes in Cantor space.
Of particular interest, for reasons that will become apparent, are the
degrees available as isolated paths through computable binary trees
that are restricted to countable width only. In this talk, I will show
that the degrees of these paths can – unlike the classical case – be
noncomputable and may in fact have very high Turing degree.

URL: http://www.comp.nus.edu.sg/~fstephan/logicseminar.html

Dilip Raghavan: Cardinal invariants above the continuum

Invitation to the Logic Seminar at the National University of Singapore

Date: Wednesday, 28 September 2016, 17:00 hrs

Room: S17#04-05, Department of Mathematics, NUS

Speaker: Dilip Raghavan.

Title: Cardinal invariants above the continuum.

URL: http://www.comp.nus.edu.sg/~fstephan/logicseminar.html

Abstract: I will summarize some recent joint work with Saharon Shelah on
cardinal invariants at uncountable regular cardinals. There are some new
consistency results as well as new theorems in ZFC. The consistency
results rely on the use Boolean ultrapowers of forcing notions. I will try
to sketch the proof of some ZFC results involving the bounding and almost
disjointness at a regular uncountable cardinal.

Ding Longyun: On generalisation of the Jayne-Rogers Theorem

Invitation to the Logic Seminar at the National University of Singapore

Date: Wednesday, 31 August 2016, 17:00 hrs

Room: S17#04-05, Department of Mathematics, NUS

Speaker: Ding Longyun

Title: On generalisation of the Jayne-Rogers Theorem

URL: http://www.comp.nus.edu.sg/~fstephan/logicseminar.html

Let X,Y be separable metrizable spaces with X analytic, and let
f be function from X to Y. We say f is Sigma-m-n if, for any
Sigma-n subset A of Y, the preimage of A under f is Sigma-m.
A theorem of Jayne-Rogers shows that, a function f is Sigma-2-2 iff
X can be decomposed into countably many Sigma-2 subsets such that
f is continuous on each of these subsets. In this talk, we will
generalize this theorem to Sigma-m-n with n leq m =3 .
We also survey the history of the study on decomposing Borel functions.