Date/Time : 07 Nov 2023 17:00
Venue : S17 #04-06 (SR1)
Speaker : Ye Jinhe , University of Oxford

A difference field is a field equipped with a given automorphism and a difference variety is the natural analogue of an algebraic varieties in this setting. Complex numbers with complex conjugation or finite fields with the Frobenius automorphism are natural examples of difference fields.

For finite fields and varieties over them, the celebrated Lang-Weil estimate gives a universal estimate of number of rational points of varieties over finite fields in terms of several notions of the complexities of the given variety. In this talk, we will discuss an analogue to Lang-Weil estimate for difference varieties in finite difference fields. The proof uses pseudofinite difference fields, where the automorphism is the nonstandard Frobenius. This is joint work with Martin Hils, Ehud Hrushovski and Tingxiang Zou.

Add to calendar :

Date/Time : 31 Oct 2023 17:00
Venue : S17 #04-06 (SR1)
Speaker : Samuel Alfaro Tanuwijaya, National University of Singapore

The talk will deal with relativised versions of the Posner Robinson theorem and explore how far one can go and how to prove these relatived versions.

Add to calendar :

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 :