Date/Time : 19 Aug 2020 17:00
Venue : via Zoom
Speaker : Cristian Calude, University of Auckland

Join Zoom Meeting https://nus-sg.zoom.us/j/96860201432?pwd=cVdwZmd2clVFaEhaTmJjaGdXMFdmdz09 Meeting ID: 968 6020 1432 Password: Is P=NP? Abstract: We present a new ternary QRNG based on measuring located value indefinite observables with probabilities <b>1/4,1/2,1/4</b> and prove that every sequence generated is maximally unpredictable, 3-bi-immune (a stronger form of bi-immunity), and its prefixes are Borel normal. The ternary quantum random digits produced by the QRNG are algorithmically transformed into quantum random bits using an alphabetic morphism which preserves all the above properties.

Add to calendar :

Date/Time : 12 Aug 2020 17:00
Venue : via Zoom
Speaker : Frank Stephan, National University of Singapore

Join Zoom Meeting https://nus-sg.zoom.us/j/94862783492?pwd=eUo0aUdialQrZkt1dDlFNnB4QmtDdz09 Meeting ID: 948 6278 3492 Password: 811969  The initial segment complexity of a measure mu at n is given by the sum over all mu(x)*C(x) with x of length n for the plain complexity C and similarly for the prefix-free Kolmogorov complexity. This talk gives the basic relations between initial segment complexity and randomness notions and lists out various open questions which arise from this work. The same work was presented at the American Institute of Mathematics in this week’s programme on Algorithmic Randomness.

Add to calendar :

Date/Time : 12 Feb 2020 17:00
Venue : S17 #04-06 SR1
Speaker : Ashutosh Kumar, NUS

Date/Time:12 Feb 2020 17:00 Venue: S17 #04-06 SR1 Speaker: Ashutosh Kumar, NUS On some problems in set-theoretic Eucildean Ramsey theory We shall discuss some questions in Euclidean Ramsey theory where techniques from set theory have played a role. Add to calendar: 

Add to calendar :

Date/Time : 29 Jan 2020 17:00
Venue : S17 #04-06 SR1
Speaker : Wang Wei, Sun Yat-Sen University, Guangzhou

Date/Time:29 Jan 2020 17:00 Venue: S17 #04-06 SR1 Speaker: Wang Wei, Sun Yat-Sen University, Guangzhou Non-standard models of arithmetic and their standard systems PA is the first order fragment of Peano’s axiomatization of the natural numbers. The natural numbers, N, is called the standard model of PA. But by compactness theorem in first order logic, there are also models of PA different from N, which are called non-standard models of arithmetic. Like in N, every element of a non-standard model M has a binary expansion, which can be regarded as the characteristic function of a subset of N. The standard system of M is the collection of all such subsets of N. It is known that standard systems of non-standard models are always Scott sets and every Scott set of cardinality less than or equal to the first uncountable cardinal is the standard system of some non-standard model. However, the general Scott set problem, whether every Scott set is the standard system of some non-standard model, remains one of the major open problems in the model theory of arithmetic. This talk will present some history of Scott set problem, as well as two constructions of non-standard models with uncountable standard systems. Add to calendar: 

Add to calendar :

Date/Time : 22 Jan 2020 17:00
Venue : S17 #04-06 SR1
Speaker : Asger Dag Toernquist, Kobenhavns Universitet

Date/Time:22 Jan 2020 17:00 Venue: S17 #04-06 SR1 Speaker: Asger Dag Toernquist, Kobenhavns Universitet Mad, med, mcg and other maximal combinatorial objects This talk is about the descriptive set theory and infinitary combinatorics. In the past 6 years, a number of long-standing problems related to the definability (in the sense of effective descriptive set theory) of so-called maximal almost disjoint (mad) families, maximal eventually different (med) families, and maximal cofinitary groups (mcg) have been solved by an array of authors. I will give an overview of these developments. Almost disjoint families are families of infinite subsets of omega where any two distinct elements of the family intersect finitely; eventually different families are families of functions from omega to omega such that any two distinct functions in the family are eventually different; and cofinitary groups are subgroups of the group of all permutations of omega with the property that all non-identity elements of the group have at most finitely many fixed points. Maximality of such objects in all cases means maximal under inclusion (among such families). A classical result due to Adrian Mathias states that no analytic infinite mad families. A slew of recent results shed light on this classical result by showing that under suitable descriptive set-theoretic regularity assumptions, there are no mad families at all (and this localizes to suitable pointclasses, especially to analytic sets). In a totally unexpected twist, Horowitz and Shelah showed in 2016 that there are Borel med families and mcg, solving a long-standing problem. I will finish the talk by discussing some related, still unsolved problems, especially the following: Is there a maximal (infinite) analytic set of pairwise Turing-incomparable reals? Add to calendar: 

Add to calendar :

Date/Time : 15 Jan 2020 17:00
Venue : S17 #04-06 SR1
Speaker : Frank Stephan, National University of Singapore

Date/Time:15 Jan 2020 17:00 Venue: S17 #04-06 SR1 Speaker: Frank Stephan, National University of Singapore Measure and Conquer for Max Hamming Distance XSAT This talk gives an overview of the joint work of the speaker’s ecent work on the Hamming XSAT problem. This problem asks for an algorithm to determine which, given an XSAT instance, determines the maximum Hamming distance between two solutions of this instance. The problem has been studied by Dahloef in 2005 in an ISAAC paper who provided an O(1.83848^n) algorithm for this problem. Later Fu, Zhu and Yin presented at JFCST 2012 an O(1.6760^n) algorithm for the related Max Hamming X3SAT problem where all clauses have at most three literals. The current paper provides for the general Max Hamming XSAT problem an O(1.4983^n) algorithm which applies also the technique “Measure and Conquer” in order to prove a better bound than the algorithm would give otherwise. Furthermore, the algorithm does not only provide the maximum Hamming distance of two solutions of the instance, but instead for each k between 0 and n the number of pairs of solutions which have Hamming distance k. For the special case Max Hamming Distant X3SAT, Hoi, Jain and Stephan have the bound O(1.3298^n) at the conference FSTTCS 2019. Add to calendar: 

Add to calendar :

Date/Time : 02 Dec 2019 17:00
Venue : S17 #06-11
Speaker : Rupert Hoelzl, University of the Bundeswehr, Munich

Date/Time:02 Dec 2019 17:00 Venue: S17 #06-11 Speaker: Rupert Hoelzl, University of the Bundeswehr, Munich Randomness for computable measures and complexity We study the possible growth rates of the Kolmogorov complexity of initial segments of sequences that are random with respect to some computable measure on the Cantor Space, the so-called proper sequences. Our main results are as follows: (1) We show that the initial segment complexity of a proper sequence X is bounded from below by a computable function (that is, X is complex) if and only if X is random with respect to some computable, continuous measure. (2) We prove that a uniform version of the previous result fails to hold: there is a family of complex sequences that are random with respect to a single computable measure such that for every computable, continuous measure mu, some sequence in this family fails to be random with respect to mu. (3) We show that there are proper sequences with extremely slow-growing initial segment complexity, that is, there is a proper sequence the initial segment complexity of which is infinitely often below every computable function, and even a proper sequence the initial segment complexity of which is dominated by all computable functions. (4) We prove various facts about the Turing degrees of such sequences and show that they are useful in the study of certain classes of pathological measures on the Cantor Space, namely diminutive measures and trivial measures. Add to calendar: 

Add to calendar :

Date/Time : 14 Nov 2019 17:00
Venue : S17 #06-11
Speaker : Thilo Weinert, National University of Singapore

Date/Time:14 Nov 2019 17:00 Venue: S17 #06-11 Speaker: Thilo Weinert, National University of Singapore Partition Relations for Linear Orders in a Choiceless Context Most Partition Relations are proved for Ordinals, not general linear orders. This is due to the Axiom of Choice which I will consequently ignore during most of the lecture. Some exceptions to the rule mentioned at the beginning can be found in a 1971 paper by Erdoes, Milner and Rado and I will present some analogous results for linear orders which are given rise to by lexicographically ordered sequences of zeros and ones. I will close by discussing an open problem in this context. This is joint work (from a few years back) with Philipp Luecke and Philipp Schlicht. Add to calendar: 

Add to calendar :

Date/Time : 07 Nov 2019 17:00
Venue : S17 #06-11
Speaker : Chong Chi Tat, National University of Singapore

Date/Time:07 Mar 2019 16:00 Venue: S17 #05-12 SR4 Speaker: Wu Bin On Large Games with Bio-social Traits This paper shows that, in a class of large games with traits model, distinguishing agent space and trait space via the nowhere equivalence condition is not only sufficient but also necessary for the existence of pure strategy Nash equilibrium and closed graph property. Furthermore, under the nowhere equivalence condition, we characterize Nash equilibria of large games with traits. Add to calendar: 

Add to calendar :