Date/Time : 02 Dec 2019 17:00
Venue : S17 #06-11
Speaker : Rupert Hoelzl, University of the Bundeswehr, Munich

Date/Time:02 Dec 2019 17:00 Venue: S17 #06-11 Speaker: Rupert Hoelzl, University of the Bundeswehr, Munich Randomness for computable measures and complexity We study the possible growth rates of the Kolmogorov complexity of initial segments of sequences that are random with respect to some computable measure on the Cantor Space, the so-called proper sequences. Our main results are as follows: (1) We show that the initial segment complexity of a proper sequence X is bounded from below by a computable function (that is, X is complex) if and only if X is random with respect to some computable, continuous measure. (2) We prove that a uniform version of the previous result fails to hold: there is a family of complex sequences that are random with respect to a single computable measure such that for every computable, continuous measure mu, some sequence in this family fails to be random with respect to mu. (3) We show that there are proper sequences with extremely slow-growing initial segment complexity, that is, there is a proper sequence the initial segment complexity of which is infinitely often below every computable function, and even a proper sequence the initial segment complexity of which is dominated by all computable functions. (4) We prove various facts about the Turing degrees of such sequences and show that they are useful in the study of certain classes of pathological measures on the Cantor Space, namely diminutive measures and trivial measures. Add to calendar: 

Add to calendar :

Date/Time : 14 Nov 2019 17:00
Venue : S17 #06-11
Speaker : Thilo Weinert, National University of Singapore

Date/Time:14 Nov 2019 17:00 Venue: S17 #06-11 Speaker: Thilo Weinert, National University of Singapore Partition Relations for Linear Orders in a Choiceless Context Most Partition Relations are proved for Ordinals, not general linear orders. This is due to the Axiom of Choice which I will consequently ignore during most of the lecture. Some exceptions to the rule mentioned at the beginning can be found in a 1971 paper by Erdoes, Milner and Rado and I will present some analogous results for linear orders which are given rise to by lexicographically ordered sequences of zeros and ones. I will close by discussing an open problem in this context. This is joint work (from a few years back) with Philipp Luecke and Philipp Schlicht. Add to calendar: 

Add to calendar :

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

Date/Time:07 Mar 2019 16:00 Venue: S17 #05-12 SR4 Speaker: Wu Bin On Large Games with Bio-social Traits This paper shows that, in a class of large games with traits model, distinguishing agent space and trait space via the nowhere equivalence condition is not only sufficient but also necessary for the existence of pure strategy Nash equilibrium and closed graph property. Furthermore, under the nowhere equivalence condition, we characterize Nash equilibria of large games with traits. Add to calendar: 

Add to calendar :

Date/Time : 31 Oct 2019 17:00
Venue : S17 #06-11
Speaker : Marat Arslanov, Kazan Federal University

Date/Time:31 Oct 2019 17:00 Venue: S17 #06-11 Speaker: Marat Arslanov, Kazan Federal University n-c.e. degrees, CEA operators and fixed-point selection functions The subjects listed in the title of my talk belong to my steady scientific interest. In my talk I will speak about my recent work in these areas and list few open problems that have arisen as a result of these studies and that I can’t answer. Note: The originally planned talk by Wu Guohua for that day will be moved to the next semester. Apologies for the short notice change. Add to calendar: 

Add to calendar :

Date/Time : 24 Oct 2019 17:00
Venue : S17 #06-11
Speaker : Yang Yue, National University of Singapore

Date/Time:24 Oct 2019 17:00 Venue: S17 #06-11 Speaker: Yang Yue, National University of Singapore Ramsey’s Theorem on trees and weak Koenig’s Lemma Ramsey’s Theorem for Pairs has been studied intensively in reverse mathematics. One of the major breakthroughs is Liu Lu’s 2012 result showing RT-2-2 does not imply WKL-0. Liu’s result not only answered an important question in reverse mathematics, the technique that he used turns out to have wider applications, for example, in Monin and Patey’s separation of SRT-2-2 and RT-2-2. In this talk, we generalize Liu’s result to tree. Let TT-2-k denote the combinatorial principle stating that every k-coloring of pairs of compatible nodes on the full binary tree has a homogeneous solution, i.e. an infinite perfect tree in which all pairs of compatible nodes have the same color. We show that over the base system RCA-0, TT-2-k doe not imply weak Koenig’s lemma. This is joint work with Chong Chitat, Li Wei and Liu Lu. Add to calendar: 

Add to calendar :

Date/Time : 17 Oct 2019 17:00
Venue : S17 #06-11
Speaker : Li Zeyong,

Date/Time:17 Oct 2019 17:00 Venue: S17 #06-11 Speaker: Li Zeyong A Complete Problem for Statistical Zero Knowledge This work by Amit Sahai and Salil Vadhan presents the first complete problem for SZK, the class of promise problems possessing statistical zero-knowledge proofs (against an honest verifier). The problem, called STATISTICAL DIFFERENCE, is to decide whether two efficiently samplable distributions are either statistically close or far apart. This gives a new characterization of SZK that makes no reference to interaction or zero knowledge. The talk (due to time constraint) will focus on the second half (and arguably the more insightful half) of the completeness theorem, that is, STATISTICAL DIFFERENCE is SZK-hard. It essentially gives a constructive proof that any promise problem possessing a statistical zero-knowledge proof can be reduced to an instance of STATISTICAL DIFFERENCE in polynomial time. Add to calendar: 

Add to calendar :

Date/Time : 10 Oct 2019 17:00
Venue : S17 #06-11
Speaker : Ashutosh Kumar, National University of Singapore

Date/Time:10 Oct 2019 17:00 Venue: S17 #06-11 Speaker: Ashutosh Kumar, National University of Singapore On partitions into null sets Given a partition P of the set of reals into Lebesgue null sets, let J be the ideal of those subsets of P whose union is null. We’ll show that, consistently, J can be countably saturated. This is a joint work with Saharon Shelah. Add to calendar: 

Add to calendar :

Date/Time : 03 Oct 2019 17:00
Venue : S17 #06-11
Speaker : Dilip Raghavan, National University of Singapore

Date/Time:03 Oct 2019 17:00 Venue: S17 #06-11 Speaker: Dilip Raghavan, National University of Singapore All ultrafilters in L(R)[U] are rapid We will show that all ultrafilters in the model L(R)[U] are rapid. This is joint work with Paul Larson. Add to calendar: 

Add to calendar :

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 :