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 :

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

Abstract: A pair (a,b) of nonzero r.e. Turing degrees is called a strong minimal pair iff the recursive Turing degree is the only common lower bound and if every nonzero Turing degree bounded by a has with b a join greater or equal a. We show that such strong minimal pairs do not exist.

Joint work with Cai Mingzhong, Liu Yiqun, Liu Yong and Peng Cheng

Add to calendar :

Date/Time : 24 Aug 2022 17:00
Venue : S17 #04-05 (SR2)
Speaker : Goh Jun Le, National University of Singapore

Abstract: We present ongoing work with Steffen Lempp, Ng Keng Meng and Mariya Soskova on the algebraic structure of the Sigma^0_2 e-degrees, i.e., the quotient structure on the Sigma^0_2 subsets of the natural numbers induced by enumeration reducibility. The Sigma^0_2 e-degrees are analogous to the r.e. Turing degrees in some ways, but an elementary difference between them was exhibited by Ahmad (1998): In the former structure there are incomparable degrees a and b such that if x < a, then x < b. (Such a and b cannot exist in the r.e. Turing degrees by the Sacks splitting theorem.) Ahmad also showed that this phenomenon cannot occur symmetrically, i.e., there cannot be incomparable degrees a and b such that x < a if and only if x < b. In contrast, we show that there are incomparable degrees a, b and c such that x < a if and only if (x < b and x < c). In other words, the ideal {x: x < a} admits an exact pair (b,c). This result constitutes progress towards our ultimate goal of algorithmically deciding the truth of all two-quantifier sentences in the Sigma^0_2 e-degrees.

Add to calendar :

Date/Time : 17 Aug 2022 17:00
Venue : S17 #04-05 (SR2)
Speaker : Wong Tin Lok, National University of Singapore

Abstract: I will present another quantifier-elimination result in arithmetic under negated induction. This gives new information about pigeonhole principles and expansions to second-order models.

Joint work with: David Belanger, CT Chong, Wei Li and Yue Yang.

Add to calendar :

Date/Time : 10 Aug 2022 17:00
Venue : S17 #04-05 (Seminar Room 2)
Speaker : Tran Chieu-Minh, National University of Singapore

Abstract:  For a bivariate P(x,y) in R[x,y] – (R[x] union R[y]), we show that for all finite subsets A of R,|P(A,A)| is greater or equal alpha |A|^(5/4) with alpha = alpha(deg P) being a real number greater than 0, P(x,y)=f(gamma u(x)+delta u(y)) or P(x,y)=f(u^m(x)u^n(y)) for some univariate f, u R[t] – </b>, constants gamma, delta in R – {0}</b> and m, n in {1,2,3,…}.

This resolves the symmetric nonexpanders classification problem proposed by de Zeeuw and is a step towards the analog for polynomials of the Erdoes-Szemeredi sumproduct Conjecture. The proofs of our results use tools from semialgebraic / o-minimal geometry.

Add to calendar :