Date/Time : 24 Oct 2023 17:00
Venue : S17 #04-06 (SR1)
Speaker : Meng-Che Ho, California State University Northridge

Classically, the word problem of a group is the set of words equal to the identity of the group, and we analyze them using Turing reductions. In this talk, we consider the word problem of a group as a computably enumerable equivalence relation (ceer), namely, two words are equivalent if and only if they are equal in the group. We compare ceers using the computable reduction: $E$ is reducible to $F$ if there is a computable function $f$ so that $iEj$ if and only if $f(i)Ff(j)$.

We will discuss some recent results and see that the landscape of word problems as ceers is very different from the classical theory. For instance, in the classical setting, any Turing degree can be realized as a word problem by first constructing a countable group and then embedding it into a finitely presented group via the Higman embedding theorem. However, we prove that in the ceer setting, there is a group $G$ whose word problem is not universal, but for any nontrivial $H$, the free product $G*H$ has a universal word problem.

This is a joint work with Uri Andrews and Luca San Mauro.

Add to calendar :

Date/Time : 17 Oct 2023 17:00
Venue : S17 #04-06 (SR1)
Speaker : Frank Stephan, National University of Singapore

Floyd and Knuth studied in their 1990 paper addition machines which are machines which can add, subtract and compare integers (<,=,>) in unit time; also the reading or writing of an integer is in unit time. They showed that multiplying and dividing can be done in linear time with six registers and asked in their Open Problem (2) whether this bound can be broken; furthermore, they asked in Open Problem (5) of their paper whether there is a register machine which can output in subquadratic time the powers of two occurring in the binary representation of an integer.

The talk answers both questions affirmatively and presents the key ideas and programs to witness this.

Add to calendar :

Date/Time : 19 Sep 2023 17:00
Venue : S17 #04-06 (SR1)
Speaker : Neoh Tzeh Yuan,

The Boolean satisfiabilty problem (SAT) is a problem with great theoretical and practical interest. While heuristic algorithms tend to work well in practice, the widely believed strong exponential time hypothesis (SETH) conjectures that there is no deterministic algorithm for SAT in time O(c^n) for some constant c < 2. On the other hand, better bounds of O(c^n) with c < 2 have been found for various restricted (but still NP-complete) instances of SAT. One such problem is 3-Occur-SAT, where every variable in the formula occurs at most 3 times. Wahlstroem presented in 2005 an algorithm which solves the problem in time O(1.1279^n) and Peng and Xiao improved it (this year’s IJCAI) to O(1.1238^n).

I will present an algorithm that gives a further improvement to O(1.1199^n). I’ll discuss the common bottleneck cases faced by previous efforts and introduce new reduction and branching rules that can circumvent these cases.

The work I present is done in an internship at NUS / SOC supervised by Sanjay Jain and Frank Stephan from July to September 2023.

Add to calendar :

Date/Time : 14 Sep 2023 17:00
Venue : S17 #04-06 (SR1)
Speaker : Jan Dobrowolski, University of Manchester

The class of NSOP1 theories, originally introduced by Dzamonja and Shelah in 2004, has been studied very intensively in the last few years since the striking discovery of an independence relation called Kim-independence by Ramsey and Kaplan (based on earlier ideas of Kim and a work of Chernikov and Ramsey), which generalises forking independence in simple theories, and retains almost all its nice properties in the class of NSOP1 theories.

I will start the talk with an overview of the notion of Kim-independence, and then I will present my joint work with Mark Kamsma on generalising Kim-independence to positive logic. In particular, I will discuss examples of positive NSOP1 theories falling into our framework such as the theory of existentially closed exponential fields (studied by Kirby and Haykazyan), the theory of fields with a generic submodule (studied by d’Elbee, Kaplan and Neuhauser) and the hyperimaginary extensions of NSOP1 theories.

Add to calendar :

Date/Time : 12 Sep 2023 17:00
Venue : S17 #04-06 (SR1)
Speaker : Borisa Kueljevic, University of Novi Sa

We will sketch the proof that MA(kappa) implies that each collection of P_c-points of size at most kappa which has a P_c-point as an RK upper bound also has a P_c-point as an RK lower bound.

This is joint work with Dilip Raghavan and Jonathan Verner.

Add to calendar :

Date/Time : 05 Sep 2023 17:00
Venue : S17 #04-06 (SR1)
Speaker : Sun Mengzhou,

Compared with end extensions, much little is known about cofinal extensions for models of fragments of PA. In particular, it is not even known known whether the elementarity of cofinal extensions can fail at some specific level. In this talk, I will try to give a complete answer. I will present a systemetic way to `compress’ the truth of M into the second-order structure of a definable cut, and as a consequence, a correspondence theorem between the first-order theory of M and the second-order theory of the cut. Through this method I will construct several models with special cofinal extension properties.

I will also show that every countable model of arithmetic fail to satisfy PA admits a non-elementary cofinal extension. It provides a model-theoretic characterization for PA in terms of cofinal extensions.

Add to calendar :

Date/Time : 29 Aug 2023 17:00
Venue : S17 #04-06 (SR1)
Speaker : Tran Chieu Minh, National University of Singapore

In a recent work, we show that if A is an open subset of SO(3,R) with sufficiently small normalized Haar measure, then mu(A^2) > 3.99 mu(A).

This was conjectured by Emmanuel Breuillard and Ben Green around 15 years ago in the context of getting optimal bounds and finding continuous counterparts of product theorems by Helfgott, Pyber-Szabo, and Breuillard-Green-Tao. The result is also related to the Brunn-Minkowski inequalities from convex geometry, the Kunze-Stein phenomenon from harmonic analysis, and the Pillay conjectures from model theory.

In this talk, I will explain these connections and discuss some ideas from the proof, which uses nonstandard analysis and neostable group theory.

(The talk is based on joint work with Yifan Jing and Ruixiang Zhang)

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

Add to calendar :

Date/Time : 10 May 2023 17:00
Venue : S17 #04-05 (SR2)
Speaker : Jan Baars,

For a Tychonov space X we define Cp(X) to be the linear subspace of R^X consisting of all real-valued continuous functions on X. Let βX be the ˇCech-Stone compactifaction of X and let X^* = βX \ X be the remainder of X. For u ∈ X^*, we denote Xu = X ∪ {u} ⊆ βX.

For the countable discrete space ω, elements of ω^* can be identified with free ultrafilters on ω. In 1990 Gul’ko proved in [3] for u, v ∈ ω^* that Cp(ωu) and Cp(ωu) are linearly home- omorphic if and only if ωu and ωv are homeomorphic. In [1] this result was generalized for finite sums of spaces ωu as follows: For n, m ≥ 1 and {u1,…,un, v1,…,vm} ⊆ ω∗, let X and Y be the direct sums of all ω_ui and ω_vi, respectively.

Then the spaces Cp(X) and Cp(Y) are linearly homeomorphic if and only X and Y are homeomorphic, in particular n = m. Gul’ko’s result does not hold for all spaces X. For example in [2] it was shown that for each ordinal space α, where ω < α < ω1 is a limit ordinal, there are u, v ∈ α^* such that Cp(αu) and Cp(αv) are linearly homeomorphic but αu and αv are not homeomorphic.

Here the references are as follows:

[1] J. Baars, On the lp-equivalence of ultrafilters, Bull. Pol. Acad. Sci. Math. Vol 70 No 1. (2022), 63–82.

[2] J. Baars and J. van Mill, Function spaces and points in ˇCech-Stone remainders, To appear in Topology Appl.

[3] S.P. Gul’ko, Spaces of continuous functions on ordinals and ultrafilters, Math. Notes, Vol. 47,4 (1990), 329–334.

Add to calendar :

Date/Time : 12 Apr 2023 17:00
Venue : via Zoom
Speaker : Daniel Max Hoffmann, University of Warsaw

Add to calendar :