Date/Time : 12 Sep 2019 17:00
Venue : S17 #06-11
Speaker : Gao Ziyuan, National University of Singapore

Date/Time:12 Sep 2019 17:00 Venue: S17 #06-11 Speaker: Gao Ziyuan, National University of Singapore The one-cop-moves game on planar graphs Cops and Robbers is a vertex-pursuit game played on graphs. In this game, a set of cops and a robber occupy the vertices of the graph and move alternately along the graph’s edges with perfect information about each other’ positions. If a cop eventually occupies the same vertex as the robber, then the cops win; the robber wins if she can indefinitely evade capture. Aigner and Fromme established that in every connected planar graph, three cops are sufficient to capture a single robber. In this paper, we consider a recently studied variant of the cops and robbers game, alternately called the one-active-cop game, one-cop-moves game or the lazy cops and robbers game, where at most one cop can move during any round. We show that Aigner and Fromme’s result does not generalize to this game variant by constructing a connected planar graph on which a robber can indefinitely evade three cops in the one-cop-moves game. This talk is based on joint work with Boting Yang (http://www2.cs.uregina.ca/~boting/). Add to calendar: 

Add to calendar :

Date/Time : 05 Sep 2019 17:00
Venue : S17 #06-11
Speaker : Samuel Alfaro Tanuwijaya,

Date/Time:05 Sep 2019 17:00 Venue: S17 #06-11 Speaker: Samuel Alfaro Tanuwijaya Pseudo-finite fields This talk will introduce pseudofinite fields and how they are axiomatized. We will see how they are infinite models of the theory of finite fields, and therefore there is no theory whose models are exactly the finite fields. Add to calendar: 

Add to calendar :

Date/Time : 29 Aug 2019 17:00
Venue : S17 #06-11
Speaker : Chong Chi Tat, National University of Singapore

Date/Time:29 Aug 2019 17:00 Venue: S17 #06-11 Speaker: Chong Chi Tat, National University of Singapore Revisiting Seetapun’s theorem with his disjunction Ramsey’s theorem RT^n_2 states that if the n-rtuples of the set of natural numbers are coloured in either red or blue, then there is an infinite subset all of whose n-tuples have the same color. The proof-theoretic strength of RT^n_2 has been a prominent line of study in reverse mathematics. The first major breakthrough was obtained by David Seetapun (Seetapun and Slaman (1995)) who showed that RT^2_2 is strictly weaker than RT^3_2. This talk will describe a proof of this theorem using the technique called “Seetapun disjunction” introduced in Chong, Slaman and Yang (2014). Add to calendar: 

Add to calendar :

Date/Time : 22 Aug 2019 17:00
Venue : S17 #06-11
Speaker : Johanna Franklin,

Date/Time:22 Aug 2019 17:00 Venue: S17 #06-11 Speaker: Johanna Franklin Degrees of isometric isomorphism for Banach spaces The degree of isomorphism of a computable presentation of a structure is the least powerful Turing degree that computes an isomorphism from this presentation onto the “standard” copy of the structure, assuming that such a copy exists. I will discuss the degrees of isometric isomorphism of two of the five types of nonzero separable L^p spaces and then consider lowness for isometric isomorphism for these spaces. Time permitting, I will discuss lowness for isometric isomorphism and lowness for isometry in a more general context. Joint work with Tim McNicholl Add to calendar: 

Add to calendar :

Date/Time : 16 Jul 2019 16:00
Venue : S17 #04-06 SR1
Speaker : Andre Nies, University of Auckland

Date/Time:16 Jul 2019 16:00 Venue: S17 #04-06 SR1 Speaker: Andre Nies, University of Auckland Random sequences of quantum bits Martin-Loef formalised in 1966 the intuitive notion of randomness of infinite sequences of bits via algorithmic tests. In this talk, we investigate what happens if we replace classical bits by quantum bits. We first provide a framework to formalise infinite sequences of quantum bits as states of a suitable C* algebra. Thereafter we introduce an analog of Martin-Loef’s notion. We show that for classical bit sequences the two notions coincide. We also discuss quantum Kolmogorov complexity for finite sequences of quantum bits and its relationship to quantum Martin-Loef randomness. Finally, we consider an effective version of the Shannan-McMillan-Breiman theorem in the quantum setting. This is joint work with Volkher Scholz. The paper is available at http://arxiv.org/abs/1709.08422. Add to calendar: 

Add to calendar :

Date/Time : 08 May 2019 17:00
Venue : S17 #04-06 SR1
Speaker : Borisa Kuzeljevic, University of Novi Sad

Date/Time:08 May 2019 17:00 Venue: S17 #04-06 SR1 Speaker: Borisa Kuzeljevic, University of Novi Sad Matrices of countable elementary submodels We present an application of the forcing notion of finite matrices whose rows consist of isomorphic countable elementary submodels of a given structure of the form $H_{\theta}$. We will explain how forcing with this poset adds a Kurepa tree. If a minor modification of the poset is considered, then the tree added is actually an almost Souslin Kurepa tree. This is a joint work with Stevo Todorcevic. Add to calendar: 

Add to calendar :

Date/Time : 17 Apr 2019 17:00
Venue : S17 #04-06 SR1
Speaker : Liu Tianyu,

Date/Time:17 Apr 2019 17:00 Venue: S17 #04-06 SR1 Speaker: Liu Tianyu Arithmetic algorithm of surreal numbers The surreal number system is a totally ordered proper class containing the real numbers as well as infinite and infinitesimal numbers. A surreal number is sometimes defined as a function from an initial segment of the ordinals into the set $(+,-)$, usually leads to an infinite sign sequence. It can also be expressed uniquely in a normal form, as $\sum_{i<\alpha} \omega^{a_i}r_i$. In this talk I will present some algorithms for addition, multiplication and division on the real field. Besides, we will cover the normal form and sign sequence of surreal numbers, which will be crucial for arithmetic algorithm of surreal numbers of length $>\omega$. Add to calendar: 

Add to calendar :

Date/Time : 10 Apr 2019 17:00
Venue : S17 #04-06 SR1
Speaker : Gao Ziyuan, National University of Singapore

Date/Time:10 Apr 2019 17:00 Venue: S17 #04-06 SR1 Speaker: Gao Ziyuan, National University of Singapore Finitely distinguishable erasing pattern languages with bounded variable frequency A pattern is a nonempty string made up of symbols from two disjoint sets, an alphabet $\Sigma$ of constant symbols and a countably infinite set $X$ of variables. The erasing pattern language $L(\pi)$ generated by a pattern $\pi$ is the set of all words over $\Sigma$ obtained by replacing all the variables of $\pi$ with arbitrary words over $\Sigma$, with the proviso that identical variables be replaced with the same string. In particular, patterns allow for repetitions of variable substrings, a feature known as backreferencing in programming languages. A distinguishing set for any pattern $\pi$ w.r.t. a class $\Pi$ of patterns containing $\pi$ is a set $D$ of words over $\Sigma$ that distinguishes $\pi$ from every other pattern $\tau$ in $\Pi$ with $L(\tau) \neq L(\pi)$ (i.e., $D \cap L(\pi) \neq D \cap L(\tau)$ whenever $L(\tau) \neq L(\pi)$). Two basic types of counting problems will be discussed: first, given any pattern $\pi$ belonging to a class $\Pi$ of patterns, does $\pi$ have a finite distinguishing set w.r.t. $\Pi$; second, what is the minimum size of a distinguishing set for $\pi$ w.r.t. $\Pi$? The latter quantity gives a measure of the information complexity of $\pi$ w.r.t. $\Pi$, and it is known as the (classical) teaching dimension of $\pi$ w.r.t. $\Pi$ in computational learning theory. We also consider the problem of determining, for any given strict partial order $\prec$ on $\Pi$ (up to equivalence of patterns) and any pattern $\pi$ belonging to $\Pi$, the minimum size of a distinguishing set for $\pi$ w.r.t. the subclass of all $\tau$ in $\Pi$ such that $\tau \not\prec \pi$; this quantity is known as the preference-based teaching dimension of $\pi$ w.r.t. $(\Pi,\prec)$. We study how the classical and preference-based teaching dimensions of patterns w.r.t. various “naturally” defined classes of patterns and strict partial orders depend on the alphabet size and the maximum number of variable repetitions in any single pattern belonging to the class. Add to calendar: 

Add to calendar :