Logic Seminar in Semester I AY 2018/2019

• Wednesday 15/08/2018, 17:00 hrs, Week 1, S17#04-05.
  Frank Stephan. Computational aspects of the hyperimmune-free degrees.
  A set A has hyperimmune-free degree, if every set B Turing equivalent to A is already truth-table equivalent to A. Equivalently, one can also say that every function f Turing reducible to A is majorised by a recursive function. Starting with a result that there is a recursive tree T with uncountably many infinite branches such that all of these have hyperimmune-free degree, the authors (Ng Keng Meng, Frank Stephan, Yang Yue and Yu Liang) investigated the overall notion of hyperimmune-free degrees, their jumps and in particular the extent to which one can strengthen the before-mentioned result. Indeed, one can achieve that all the infinite branches on the tree T are not only hyperimmune-free but also jump-traceable, Schnorr trivial and of either minimal or recursive Turing degree.
  A preliminary conference version of the paper is available from Ng Keng Meng's homepage.
  
  
• Wednesday 22/08/2018, 17:00 hrs, Week 2, S17#04-05.
  Public Holiday, Hari Raya Haji. No Logic Seminar.
  
  
• Wednesday 29/08/2018, 17:00 hrs, Week 3, S17#04-05.
  Venkatesh Srinivasan. Scalable misinformation prevention in social networks.
  We consider misinformation propagating through a social network and study the problem of its prevention. In this problem, a ``bad'' campaign starts propagating from a set of seed nodes in the network and we use the notion of a limiting (or ``good'') campaign to counteract the effect of misinformation. The goal is then to identify a subset of k users that need to be convinced to adopt the limiting campaign so as to minimize the number of people that adopt the ``bad'' campaign at the end of both propagation processes.
  We present ``Reverse Prevention Sampling (RPS)'', an algorithm that provides a scalable solution to the misinformation prevention problem. Our theoretical analysis shows that RPS returns a good approximate solution with high probability. Furthermore, the time complexity of RPS substantially improves upon the previously best-known algorithm for this problem. We experimentally evaluate RPS on large datasets and show that it outperforms the state-of-the-art solution by several orders of magnitude in terms of running time. Our work demonstrates that misinformation prevention can be made practical while still offering strong theoretical guarantees.
  This is joint work with Michael Simpson and Alex Thomo, University of Victoria. The paper is available as a technical report.
  
  
• Monday 03/09/2018, 15:00 hrs, Week 4, OOM2#04-02.
  Algorithms and Theory Seminar at SoC.
  Sibylle Schwarz. Ethitcal decision making by logic programs.
  The formalization of ethical principles in human decision making gains increasing attention, for example due to recent developments in autonomous driving. The moral permissibility of actions is illustrated by the Trolley Problem.
  The weak completion semantics is a three-valued fixpoint semantics for logic programs based on Lukasiewicz logic. It is more adequate to human reasoning than previous approaches.
  In the talk, the weak completion semantics is introduced and several variants of the Trolley Problem are formalized as logic programs under this semantics.
  
  
• Wednesday 05/09/2018, 17:00 hrs, Week 4, S17#04-05.
  Chong Chi Tat. Cohesiveness for trees.
  The combinatorial principle COH for natural numbers is a key component in the decomposition of Ramsey's theorem for pairs (RT²₂) and has been extensively studied in reverse mathematics. It is known in particular that COH is Π¹₁-conservative over RCA₀ plus Σ⁰₂-bounding (Chong, Slaman and Yang). The tree theorem for pairs (TT²₂) is a generalization of RT²₂ to the Cantor space, and there is a corresponding decomposition of TT²₂ with an analog of COH, called the cohesive tree principle, as a key component. In this talk we give a sketch of the theorem that this principle is Π¹₁-conservative over RCA₀ plus Σ⁰₂-bounding and the totality of Ackermann's function.
  This is joint work with Li Wei, Liu Lu and Yang Yue.
  
  
• Wednesday 12/09/2018, 17:00 hrs, Week 5, S17#04-05.
  Boriša Kuzeljević. P-ideal dichotomy and some versions of the Souslin's Hypothesis.
  P-ideal dichotomy is a combinatorial set theoretic principle which has many consequences on the universe of set theory. For example, it implies the Souslin's Hypothesis, Singular Cardinals Hypothesis, and Projective Determinacy. In this talk we will analyze a relationship between the P-ideal dichotomy and the statement that all Aronszajn trees can be embedded into the rational line.
  This is joint work with Stevo Todorčević.
  
  
• Wednesday 19/09/2018, 17:00 hrs, Week 6, S17#04-05.
  Ashutosh Kumar. Saturated null and meager ideal.
  We will sketch some ideas behind the proof of the following: The null and the meager ideal could both be somewhere countably saturated.
  This is joint work with Saharon Shelah. The paper is available at the author's homepage.
  
  
• Wednesday 03/10/2018, 17:00 hrs, Week 7, S17#04-05.
  Rupert Hölzl. Degrees of randomized computability.
  In this survey we discuss work of Levin and V'yugin on collections of sequences that are non-negligible in the sense that they can be computed by a probabilistic algorithm with high probability. More precisely, Levin and V'yugin introduced an ordering on collections of sequences that are closed under Turing equivalence. Roughly speaking, given two such collections A and B, A is less than B in this ordering if A-B is negligible. The degree structure associated with this ordering, the Levin-V'yugin degrees (or LV-degrees) can be shown to be a Boolean algebra, and in fact a measure algebra.
  We demonstrate the interactions of this work with recent results in computability theory and algorithmic randomness: First, we recall the definition of the Levin-V'yugin algebra and identify connections between its properties and classical properties from computability theory. In particular, we apply results on the interactions between notions of randomness and Turing reducibility to establish new facts about specific LV-degrees, such as the LV-degree of the collection of 1-generic sequences, that of the collection of sequences of hyperimmune degree, and those collections corresponding to various notions of effective randomness. Next, we provide a detailed explanation of a complex technique developed by V'yugin that allows the construction of semi-measures into which computability-theoretic properties can be encoded. We provide examples of the uses of this technique by explicating and extending V'yugin's results about the LV-degrees of the collection of Martin-Löf random sequences and the collection of sequences of DNC degree, as well as results concerning atoms of the LV-degrees.
  The slides are available from Rupert Hölzl's homepage. This is joint work with Christopher P. Porter.
  
  
• Wednesday 10/10/2018, 17:00 hrs, Week 8, S17#04-05.
  Liu Lu. Combinatorial implication of computability theory.
  We prove that the relativised version of a naturally arisen computability theoretic question (yet open) is equivalent to a combinatorial question.
  
  
• Wednesday 17/10/2018, 17:00 hrs, Week 9, S17#04-05.
  Dilip Raghavan. Order dimension.
  We will present some results on the order dimension of various partial orders, focusing on partial orders which are locally countable.
  This is joint work with Kojiro Higuchi, Steffen Lempp and Frank Stephan.
  
  
• Wednesday 24/10/2018, 17:00 hrs, Week 10, S17#04-05.
  Frank Stephan. A fast exponential time algorithm for Max Hamming Distance X3SAT.
  SAT is the problem which asks whether a given list of clauses in n Boolean variables can be satisfied by an assignment to the variables which is common for all clauses, XSAT is the variant of SAT which asks the same, but requires in addition that in each clause exactly one literal is true; X3SAT is the corresponding problem with the additional constraint that every clause contains up to three literals only. Now the problem "Max Hamming Distance X3SAT" asks for the maximum Hamming distance taken by two solutions of a given instance. X3SAT can be solved only in exponential time, but the corresponding exponential time algorithm is quite fast, an algorithm of Magnus Wahlström from 2007 provides time O(1.0984ⁿ). The problem to find pairs of solutions of maximum Hamming distance is more difficult: The up to now best known bound is by Fu, Zhou and Yin of time O(1.6760ⁿ) and the contribution of the here presented work is to bring this down to O(1.3298ⁿ).
  This is joint work with Gordon Hoi and the paper is available here.
  
  
• Wednesday 31/10/2018, 17:00 hrs, Week 11, S17#04-05.
  Kihara Takayuki. BQO-Wadge theory on ultrametric spaces.
  Recently, Kihara and Montalban have, in a joint paper, given a complete classification of the BQO-valued Borel maps on Baire space in terms of the Wadge degrees. Roughly speaking, the authors have shown that any BQO-valued Borel map on Baire space is generated by (suitable iterations of) very simple construction principles, and is completely classified by detecting how it is constructed.
  In this talk, we extend the theory of Wadge degrees on BQO-valued maps to arbitrary (possibly non-separable) completely ultrametrizable spaces. We apply suitable variants of computability theory over arbitrary uncountable cardinals to generalize Kihara-Montalban's complete classification of the BQO-valued Borel maps to the non-separable setting.
  
  
• Wednesday 07/11/2018, 17:00 hrs, Week 12, S17#04-05.
  George Barmpalias. Compression of data streams down to their information content.
  According to Kolmogorov complexity, every finite binary string is compressible to a shortest code - its information content - from which it is effectively recoverable. We investigate the extent to which this holds for infinite binary sequences (streams). We devise a new coding method which uniformly codes every stream X into an algorithmically random stream Y, in such a way that the first n bits of X are recoverable from the first I(X[1..n]) bits of Y, where I is any partial computable information content measure which is defined on all prefixes of X, and where X[1..n] is the initial segment of X of length n. As a consequence, if g is any computable upper bound on the initial segment prefix-free complexity of X, then X is computable from an algorithmically random Y with oracle-use at most g. Alternatively (making no use of such a computable bound g) one can achieve an oracle-use bounded above by K(X[1..n])+log(n). This provides a strong analogue of Shannon's source coding theorem for algorithmic information theory.
  This is joint work with Andrew Lewis-Pye and the paper is available as a technical report on http://arxiv.org/abs/1710.02092.
  
  
• Wednesday 14/11/2018, 17:00 hrs, Week 13, S17#04-05.
  Konstantin Slutsky. Orbit equivalences of Borel flows.
  The purpose of this talk is to provide an overview of the orbit equivalence theory of Borel Rⁿ-flows. An orbit equivalence of two group actions is a bijective map between phase spaces that maps orbits onto orbits. Such maps are often further required to posses regularity properties depending on the category of group actions that is being considered. For example, Borel dynamics deals with Borel orbit equivalences, ergodic theory considers measure-preserving maps, topological dynamics assumes continuity, etc.
  Since its origin in 1959 in the work of Henry Abel Dye, the concept of orbit equivalence has been studied quite extensively. While traditionally larger emphasis is given to actions of discrete groups, in this talk we concentrate on free actions of Rⁿ-flows taking the viewpoint of Borel dynamics.
  For a free Rⁿ-action, an orbit can be identified with an "affine" copy of the Euclidean space, which allows us to transfer any translation invariant structure from Rⁿ onto each orbit. The two structures of utmost importance will be that of Lebesgue measure and standard Euclidean topology. One may then consider orbit equivalence maps that furthermore preserve these structures on orbits. Resulting orbit equivalences are called Lebesgue orbit equivalence (LOE) and time-change equivalence respectively.
  It turns out that properties of LOE maps correspond most closely to those of orbit equivalence maps between their discrete counterparts - free Zⁿ actions. We illustrate this by outlining a proof of the analog for Rⁿ-flows of Dougherty-Jackson-Kechris classification of hyperfinite equivalence relations.
  Orbit equivalences of flows often arise as extensions of maps between cross sections - Borel sets that intersect each orbit in a non-empty countable set. Furthermore, strong geometric restrictions on cross-sections are often necessary. As a concrete example, we explain why one-dimensional R-flows posses cross sections with only two distinct distances between adjacent points, and show how this implies classification of R-flows up to LOE.
  We conclude the talk with an overview of time-change equivalence, emphasizing the difference between Borel dynamics and ergodic theory and mentioning several open problems.
  The interest reader is referred to the technical report on http://arxiv.org/abs/1504.00958.
  
  
• Thursday 22/11/2018, 17:00 hrs, S17#04-05.
  Xu Tianyi. Homotopy-theoretic aspects of type theory.
  We will review induction principles and define general inductive types. Equality types of some inductive types will then be discussed, using their respective induction principles. We will then explore the homotopy-theoretic interpretations of types by regarding equality types as path spaces. This then leads to higher inductive types, which will be briefly discussed.