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 :