Date/Time : 14 Oct 2020 17:00
Venue : via Zoom
Speaker : Tran Chieu-Minh,

Join Zoom Meeting https://nus-sg.zoom.us/j/96860201432?pwd=cVdwZmd2clVFaEhaTmJjaGdXMFdmdz09 Meeting ID: 968 6020 1432 Password: Is P=NP? Abstract:  Zarankiewicz’s problem in graph theory asks to determine the largest possible number of edges |E| in a bipartite graph G = (V_1, V_2; E) with the parts V_1 and V_2 containing n_1 and n_2 vertices, respectively, and such that G contains no complete bipartite subgraphs on k vertices. Graphs definable in o-minimal (or more generally distal structures) enjoy stronger bounds than general graphs, providing an abstract setting for the Szemeredi-Trotter theorem and related incidence bounds. We obtain almost optimal upper and lower bounds for hypergraphs definable in locally modular o-minimal structures, along with some applications to incidence counting (e.g. the number of incidences between points and boxes with axis parallel sides on the plane whose incidence graph is K_{k,k}-free is almost linear). We explain how the exponent appearing in these bounds is tightly connected to the trichotomy principle in o-minimal structures. Joint work with Abdul Basit, Artem Chernikov, Sergei Starchenko and Terence Tao.

Add to calendar :

Date/Time : 30 Sep 2020 17:00
Venue : via Zoom
Speaker : Vasco Brattka, Universtiaet der Bundeswehr, Muenchen

Join Zoom Meeting https://nus-sg.zoom.us/j/96860201432?pwd=cVdwZmd2clVFaEhaTmJjaGdXMFdmdz09 Meeting ID: 968 6020 1432 Password: Is P=NP? Abstract:   We discuss the question whether there is a weakest unsolvable mathematical problem. In recent years the Weihrauch lattice has been established as a suitable computability theoretic framework to analyze the uniform computational content of problems from many different fields of mathematics. Here we answer a question by Schroeder, whether there is a weakest discontinuous problem with respect to the continuous version of Weihrauch reducibility. We introduce the discontinuity problem, and we show that it is reducible exactly to the effectively  discontinuous problems, defined in a suitable way. However, in which sense this answers Schroeder’s question sensitively depends on the axiomatic framework that is chosen and it is a positive answer if we work in Zermelo- Fraenkel set theory with dependent choice and the axiom of determinacy. On the other hand, using the axiom of choice, one can construct problems which are discontinuous, but not effectively so.   Hence, the exact structure of the “bottom” of the Weihrauch lattice sensitively depends on the axiomatic setting that we choose.   We prove our result using Wadge games for mathematical problems and while the existence of a winning strategy for player II characterizes continuity of the problem (as already shown by Nobrega and Pauly), the existence of a winning strategy for player I characterizes effective discontinuity of the problem. We also provide further insights into the algebraic nature of the discontinuity problem. For one we show that the parallelization of the discontinuity problem is exactly the non-computability problem that was studied before. One the other hand, we introduce a new algebraic operation in the Weihrauch lattice that we call summation and which is the dual operation to parallelization. While parallelization can be seen as an analogue of the bang operator in linear logic, summation can be seen as an analogue of the question mark operator. It turns out that the discontinuity problem can be obtained as summation of a number of well-known problems in the Weihrauch lattice, such as the (lesser) limited problem of omniscience and variants thereof. More generally, we study the action of the monoid formed by parallelization and summation on the Weihrauch lattice, and we prove that this action can lead to at most five different Weihrauch degrees, which (in the maximal case) are always organized in a pentagon. We show that the discontinuity problem appears as the bottom of several natural such pentagons. This leads to further interesting characterizations of the discontinuity problem.

Add to calendar :

Date/Time : 16 Sep 2020 17:00
Venue : via Zoom
Speaker : Ye Jinhe,

Join Zoom Meeting https://nus-sg.zoom.us/j/96860201432?pwd=cVdwZmd2clVFaEhaTmJjaGdXMFdmdz09 Meeting ID: 968 6020 1432 Password: Is P=NP? Abstract: For any field K, we introduce natural topologies on K-points of varieties over K, which is defined to be the weakest topology such that etale morphisms are open. This topology turns out to be natural in a lot of settings. For example, when K is algebraically closed, it is easy to see that we have the Zariski topology and it picks up the valuation topology in many Henselian valued fields. Moreover, many topological properties correspond to the algebraic properties of the field. As an application, we will show large stable fields are separably closed, a special case of the stable fields conjecture. This is joint work with Will Johnson, Chieu-Minh Tran and Erik Walsberg.

Add to calendar :

Date/Time : 09 Sep 2020 17:00
Venue : via Zoom
Speaker : Ming Xiao, National University of Singapore

Join Zoom Meeting https://nus-sg.zoom.us/j/96860201432?pwd=cVdwZmd2clVFaEhaTmJjaGdXMFdmdz09 Meeting ID: 968 6020 1432 Password: Is P=NP? Abstract:  In 1948, Horn and Tarski conjectured whether the sigma-finite chain condition and sigma-bounded chain condition are equivalent. The first counterexample was given by Thummel in 2012 and then a Borel counterexample was given by Todorvevic in 2014. Both examples belong to a class of poset called “Todorvevic ordering” T(X) over topological spaces X. In this talk, I will illustrate a satisfactory condition for a topological space X making the corresponding poset T(X) fail to have a countable Borel partition witnessing the sigma-finite chain condition, although it may still be witnessed by non-Borel partitions. The content of this talk is going to be the same as the one I gave in a seminar at the Chinese Academy of Sciences last year and is also a part of my Ph.D. dissertation.

Add to calendar :

Date/Time : 26 Aug 2020 17:00
Venue : via Zoom
Speaker : Gordon Hoi,

Join  Zoom Meeting: https://nus-sg.zoom.us/j/96860201432?pwd=cVdwZmd2clVFaEhaTmJjaGdXMFdmdz09 Meeting ID: 968 6020 1432 Password: Is P=NP? The Exact Satisfiability problem, XSAT, is defined as the problem of finding a satisfying assignment to a formula in CNF such that there is exactly one literal in each clause assigned to be 1 and the other literals in the same clause are set to 0. If we restrict the length of each clause to be at most 3 literals, then it is known as the X3SAT problem. In this paper, we consider the problem of counting the number of satisfying assignments to the X3SAT problem, which is also known as #X3SAT. The current state of the art exact algorithm to solve #X3SAT is given by Dahlloef, Jonsson and Beigel and runs in O(1.1487^n), where n is the number of variables in the formula. In this paper, we propose an exact algorithm for the #X3SAT problem that runs in O(1.1120^n) with very few branching cases to consider, by using a result from Monien and Preis to give us a bisection width for graphs with at most degree 3. URL: http://www.comp.nus.edu.sg/~fstephan/logicseminar.html

Add to calendar :

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 :