Meeting ID: 830 4925 8042 Passcode: Compute z where z is the first number equal to x

- Wednesday 10/08/2022, 17:00 hrs, Week 1,
Department of Mathematics, Room S17#04-05.

**Tran Chieu-Minh**.

*O-minimal Methods and Generalized Sum-Product Phenomena*.

For a bivariate**P(x,y) ∈ R[x,y] ∖ (R[x] ∪ R[y])**, we show that for all finite**A ⊆ R**,**|P(A,A)| ≥ α|A|**with^{5/4}**α = α(deg P) ∈ R**unless^{>0}**P(x,y)=f(γ u(x)+δ u(y))**or**P(x,y)=f(u**for some univariate^{m}(x)u^{n}(y))**f, u ∈ R[t] ∖ R**, constants**γ, δ ∈ R ∖ {0}**and**m, n ∈ {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 Erdös-Szemerédi sumproduct Conjecture.

The proofs of our results use tools from semialgebraic / o-minimal geometry.

- Wednesday 17/08/2022, 17:00 hrs, Week 2,
Department of Mathematics, Room S17#04-05.
**Wong Tin Lok**.*Another quantifier-elimination result in arithmetic under negated induction*.

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.

This work is joint with David Belanger, CT Chong, Wei Li and Yue Yang.

- Wednesday 24/08/2022, 17:00 hrs, Week 3,
Department of Mathematics, Room S17#04-05.

**Goh Jun Le**.*An exact pair in the*.**Σ**enumeration degrees^{0}_{2}

We present ongoing work with Steffen Lempp, Ng Keng Meng and Mariya Soskova on the algebraic structure of the**Σ**e-degrees, i.e., the quotient structure on the^{0}_{2}**Σ**subsets of the natural numbers induced by enumeration reducibility. The^{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^{0}_{2}**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 if**x < a**iff**x < b**. In contrast, we show that there are incomparable degrees**a**,**b**and**c**such that if**x < a**if and only if both**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**Σ**e-degrees.^{0}_{2}

- Thursday 31/08/2022, 17:00 hrs, Week 4,
Department of Mathematics, Room S17#04-05.

**Yang Yue**.*The Strong Minimal Pair Problem*.

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 equal**a**. We show that such strong minimal pairs do not exist.

This is joint work with Cai Mingzhong, Liu Yiqun, Liu Yong and Peng Cheng.

- Wednesday 07/09/2022, 17:00 hrs, Week 5,
Department of Mathematics, Room S17#04-05.

**Liao Yuke**.*A computable coloring without***Π**witness with apartness for Hindman theorem.^{0}_{3}

We construct a computable coloring function such that any**Π**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".^{0}_{3}

- Wednesday 14/09/2022, 17:00 hrs, Week 6,
Department of Mathematics, Room S17#04-05.

**Ammar Fathin Sabili**.*Alternating automatic register machines.*

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**log**steps. Furthermore, we also show that padding the input with a polynomial-size string allows to recognise exactly the sets in the polynomial hierarchy using^{*}n + O(1)**log**steps. These results illustrate the power of alternation when combined with computations involving automatic relations.^{*}n + O(1)

This is joint work with Gao Ziyuan, Sanjay Jain, Li Zeyong and Frank Stephan. A technical report is available on https://arxiv.org/abs/2111.04254.

- Wednesday 28/09/2022, 17:00 hrs, Week 7,
Zoom 830 4925 8042, Passcode z=x3+y3, replace z as indicated above.

**No talk**.

- Wednesday 05/10/2022, 17:00 hrs, Week 8,
Department of Mathematics, Room S17#04-05.

**Yang Yue**.*Between***Σ**and_{1}**Σ**Induction._{2}

Yang Yue will talk about his past and concurrent research in Reverse Mathematics and provide the background of other researchers on the same topic, please see the linked pdf-file for more details.

- Wednesday 12/10/2022, 17:00 hrs, Week 9,
Department of Mathematics, Room S17#04-05.

**Pétér Komjáth**.

- Wednesday 19/10/2022, 17:00 hrs, Week 10,
Zoom 830 4925 8042, Passcode z=x3+y3, replace z as indicated above.

- Wednesday 26/10/2022, 17:00 hrs, Week 11,
Zoom 830 4925 8042, Passcode z=x3+y3, replace z as indicated above.

**Sun Mengzhou**.

- Wednesday 02/11/2022, 17:00 hrs, Week 12,
Zoom 830 4925 8042, Passcode z=x3+y3, replace z as indicated above.

**Wu Guohua**.

- Wednesday 09/11/2022, 17:00 hrs, Week 13,
Zoom 830 4925 8042, Passcode z=x3+y3, replace z as indicated above.

**(Visitor of Tran Chieu-Minh)**.