Date/Time : 16 Nov 2022 16:00
Venue : S15 #03-15 (Seminar Room L3)
Speaker : Cristian Calude, University of Auckland

Abstract: We construct a class of 3-dimensional photonic quantum random number generators and prove that each generates maximally unpredictable digits via measurements that are robust to errors. In particular, every sequence generated is strongly incomputable; hence its quality is provable better than that of every pseudo-random sequence. We also briefly contrast 2-dimensional and 3-dimensional quantum random number generators, discuss photonic implementations and show the superiority of the latter ones. These results suggest that incomputability in physics is real and practically useful.

Add to calendar :

Date/Time : 09 Nov 2022 17:15
Venue : S17 #04-05 (SR2)
Speaker : Benjamin T Castle, Ben Gurion University of the Negev

Abstract: Motivated by recent progress toward Zilber’s Restricted Trichotomy Conjecture, we study reducts of the complex field up to interdefinability over parameters. Precisely, we will consider structures of the form (C, P_1,…,P_n), where C is set of complex numbers and the P_i are polynomial maps of potentially different arities.   Somewhat surprisingly, our main result states that almost all such structures (in a precise sense) are interdefinable. The proof uses a mix of tools from geometric stability theory, combinatorics, and algebraic geometry.

This is joint work with Chieu-Minh Tran.

Add to calendar :

Date/Time : 02 Nov 2022 17:00
Venue : S17 #04-05 (SR2)
Speaker : Wu Guohua, Nanyang Technological University

Abstract: Many constructions in rings involve applications of various axioms, which guarantee the existence of wanted objects. In this talk, I will present examples of such constructions, and show how these axioms are applied and really needed.

Add to calendar :

Date/Time : 26 Oct 2022 17:00
Venue : S17 #04-05 (SR2)
Speaker : Sun Mengzhou, National University of Singapore

Abstract: Paris and Kirby showed that a countable model satisfies B Sigma_{n+2} if and only if it has an (n+2)-elementary proper end extension. Later Kaufman asked whether we can always end extend countable models of B Sigma_{n+2} to some model of B Sigma_{n+1}. We briefly discuss what we have now related to this question and what is the difficulty here.

Add to calendar :

Date/Time : 19 Oct 2022 17:00
Venue : S17 #04-05 (SR2)
Speaker : Abdul Basit,

Abstract: The shatter function, a combinatorial function associated to a family of sets, is an important measure of its complexity. For example, it is related to the popular notions of VC dimension and VC density. We show that the shatter function of a semilinear family (i.e., a family definable in (R, + , <)) is asymptotic to a polynomial. This implies, in particular, that any semilinear family has integer VC density, which confirms a conjecture by Artem Chernikov.

This is joint work with Tran Chieu Minh

Add to calendar :

Date/Time : 12 Oct 2022 17:00
Venue : S17 #04-05 (SR2)
Speaker : Frank Stephan, National University of Singapore

The talk will present selected results from the joint work of Andre Nies and Frank Stephan on complexity of measures aThe talk will present selected results from the joint work of Andre Nies and Frank Stephan on complexity of measures as it is found on https://arxiv.org/abs/1902.07871s it is found on https://arxiv.org/abs/1902.07871

Add to calendar :

Date/Time : 05 Oct 2022 17:00
Venue : S17 #04-05 (SR2)
Speaker : Yang Yue, National University of Singapore

Abstract: Yang Yue will talk about his past and concurrent research in Reverse Mathematics and also provide the background of other researchers on the same topic. Please see the abstract on

https://www.comp.nus.edu.sg/~fstephan/logicseminar20221005abs.pdf

Add to calendar :

Date/Time : 14 Sep 2022 17:00
Venue : S17 #04-05 (SR2)
Speaker : Ammar Fathin Sabili, National University of Singapore

Abstract: We introduce and study a new computation model called an Alternating Automatic Register Machine (AARM). An AARM possesses a basic features of a conventional register machine and an alternating Turing machine, but can carry out computations using bounded automatic relations in a single step. One particular finding is that an AARM can recognize some NP-complete problems, including CNF-SAT (using a particular encoding), in logstar n + O(1) steps. Furthermore, we also show that padding the input with a polynomial-size string will recognize polynomial hierarchy in also logstar n + O(1) steps. These results illustrate the power of alternation when combined with computations involving automatic relations.

Add to calendar :

Date/Time : 07 Sep 2022 17:00
Venue : S17 #04-05 (SR2)
Speaker : Liao Luke,

Abstract:  We construct a computable coloring function such that any Pi^0_3 set with apartness can not be a witness of Hindman theorem for this coloring. And we can modify the coloring function and drop the condition “with apartness”.

Add to calendar :