Logic Seminar in Semester I AY 2020/2021

• Wednesday 12/08/2020, 17:00 hrs, Week 1, S17#04-06.
  Frank Stephan Initial Segment Complexity for Measures - Results and Open Problems.
  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.
  This is joint work with Andre Nies.
  The paper is availbale as a technical report on http://arxiv.org/abs/1902.07871. The slides are available as a pdf-file and as a ps-file.
  
  
• Wednesday, 19/08/2020, 17:00 hrs, Week 2, Zoom 968 6020 1432.
  Cristian Calude. A New Quantum Random Number Generator Certified by Value Indefiniteness.
  We present a new ternary QRNG based on measuring located value indefinite observables with probabilities 1/4,1/2,1/4 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.
  
  
• Wednesday 26/08/2020, 17:00 hrs, Week 3, Zoom 968 6020 1432.
  Gordon Hoi. A faster exact algorithm to count X3SAT solutions.
  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 Dahllöf, 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.
  This is joint work with Sanjay Jain and Frank Stephan.
  
  
• Wednesday 02/09/2020, 17:00 hrs, Week 4, Zoom 968 6020 1432.
  No logic seminar.
  
  
• Wednesday 09/09/2020, 17:00 hrs, Week 5, Zoom 968 6020 1432.
  Ming Xiao. A Borel Chain Condition of T(X).
  In 1948, Horn and Tarski conjectured whether the σ-finite chain condition and σ-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 σ-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.
  
  
• Wednesday 16/09/2020, 17:00 hrs, Week 6, Zoom 968 6020 1432.
  Ye Jinhe. The étale open topology.
  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 étale 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.
  
  
• Wednesday 30/09/2020, 17:00 hrs, Week 7, Zoom 968 6020 1432.
  Vasco Brattka. The Discontinuity Problem.
  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 Schröder, 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 Schröder'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.
  The slides are available.
  
  
• Wednesday 07/10/2020, 17:00 hrs, Week 8, Zoom 968 6020 1432.
  Wu Guohua. Splittings.
  I will present a survey of splittings in sets and in degrees. Downey-Stob's long paper in 1993 provides a comprehensive and updated survey. In this talk, I first recall some classical theorems on this topic, both ideas and techniques, and following this, I will present some results along this line being done in the last few years.
  
  
• Wednesday 14/10/2020, 17:00 hrs, Week 9, Zoom 968 6020 1432.
  Tran Chieu-Minh. Incidence counting and trichotomy in o-minimal structures.
  Zarankiewicz's problem in graph theory asks to determine the largest possible number of edges |E| in a bipartite graph G = (V₁, V₂; E) with the parts V₁ and V₂ containing n₁ and n₂ 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 Szemerédi-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.
  
  
• Wednesday 21/10/2020, 17:00 hrs, Week 10, Zoom 968 6020 1432.
  Rupert Hölzl. Monte Carlo Computability.
  We introduce Monte Carlo computability as a probabilistic concept of computability on infinite objects and prove that Monte Carlo computable functions are closed under composition. We then mutually separate the following classes of functions from each other: the class of multi-valued functions that are non-deterministically computable, that of Las Vegas computable functions, and that of Monte Carlo computable functions. We give natural examples of computational problems witnessing these separations. As a specific problem which is Monte Carlo computable but neither Las Vegas computable nor non-deterministically computable, we study the problem of sorting infinite sequences that was recently introduced by Neumann and Pauly. Their results allow us to draw conclusions about the relation between algebraic models and Monte Carlo computability.
  
  
• Wednesday 28/10/2020, 17:00 hrs, Week 11, Zoom 968 6020 1432.
  Liao Yuke. Computability of the Julia set.
  TTE-computable is one of the major definitions of computable real functions. We focus on a generalisation of TTE and check the basic cases of computability of Julia sets. We prove quadratic polynomials with Siegel disc incomputable in TTE is still incomputable in generalisation.
  
  
• Wednesday 04/11/2020, 17:00 hrs, Week 12, Zoom 968 6020 1432.
  Andre Nies. Weak reducibilities on the K-trivial sets.
  The K-trivial sets are antirandom in the sense that the initial segment complexity in terms of prefix-free Kolmogorov complexity K grows as slowly as possible. Chaitin introduced this notion in about 1975, and showed that each K-trivial is Turing below the halting set. Shortly after, Solovay proved that a K-trivial set can be noncomputable.
  In the past two decades, many alternative characterisations of this class have been found: properties such as being low for K, low for Martin-Löf (ML) randomness, and a basis for ML randomness, which state in one way or the other that the set is close to computable.
  Initially, the class of noncomputable K-trivials appeared to be amorphous. More recently, evidence of an internal structure has been found. Most of these results can be phrased in the language of a mysterious reducibility on the K-trivials which is weaker than Turing's: A is ML-below B if each ML-random computing B also computes A.
  Bienvenu, Greenberg, Kucera, Nies and Turetsky (JEMS 2016) showed that there an ML-complete K-trivial set. Greenberg, Miller and Nies (JML 2019) established a dense hierarchy of subclasses of the K-trivials based on fragments of Omega computing the set, and each such subclass is an initial segment for ML. More recent results generalise these approaches using so-called cost functions. They also show that each K-trivial set is ML-equivalent to a c.e. K-trivial.
  Alternative reducibilities on the K-trivials will be considered near the end of the talk. One of them is related to the extreme lowness notion of strong jump traceability, and appears to be orthogonal to ML-reducibility. Very recent work with Greenberg and Turetsky provides manyfold characterisations in terms of cost functions, and random oracles.
  The slides are available as a pdf-file.
  
  
• Wednesday 11/11/2020, 17:00 hrs, Week 13, Zoom 968 6020 1432.
  Philipp Schlicht. Structural results about Π¹₁ and Σ¹₂ sets.
  Similarities between c.e., Π¹₁ and Σ¹₂ sets can be explained by representing Π¹₁ and Σ¹₂ sets as c.e. with respect to a transfinite enumeration procedure. This representation is important for classical results about Π¹₁ and Σ¹₂ sets, but also for recent results, for instance about randomness at the level of Π¹₁ by Hjorth and Nies and structural results about Σ¹₂ sets by Chong, Wu and Yu.
  In the main result, we calculate the lengths of enumerations. More precisely, we isolate a certain countable ordinal tau and show that the length of an enumeration of a Π¹₁ or Σ¹₂ set either equals ω₁ or is below τ, and τ is optimal. This ordinal has many other interesting characterisations. For example, we show that τ is the optimal bound for the countable ranks of wellfounded Σ¹₂ relations, in analogy with the Kunen-Martin theorem. We will further touch on related structural problems such as calculating Borel ranks of Π¹₁ and Σ¹₂ Borel sets.
  This is joint work with Philip Welch and Merlin Carl. The slides are available on Philipp Schlicht's homepage.