Logic Archives - Page 16 of 17

Seminars: Logic

Date
Time
Venue

Speaker
Affiliation
Title of Talk

31 Oct 2019
17:00
S17 #06-11

Marat Arslanov
Kazan Federal University
n-c.e. degrees, CEA operators and fixed-point selection functions

n-c.e. degrees, CEA operators and fixed-point selection functions

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 :

24 Oct 2019
17:00
S17 #06-11

Yang Yue
National University of Singapore
Ramsey’s Theorem on trees and weak Koenig’s Lemma

Ramsey’s Theorem on trees and weak Koenig’s Lemma

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 :

17 Oct 2019
17:00
S17 #06-11

Li Zeyong

A Complete Problem for Statistical Zero Knowledge

A Complete Problem for Statistical Zero Knowledge

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 :

10 Oct 2019
17:00
S17 #06-11

Ashutosh Kumar
National University of Singapore
On partitions into null sets

On partitions into null sets

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 :

03 Oct 2019
17:00
S17 #06-11

Dilip Raghavan
National University of Singapore
All ultrafilters in L(R)[U] are rapid

All ultrafilters in L(R)[U] are rapid

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 :

12 Sep 2019
17:00
S17 #06-11

Gao Ziyuan
National University of Singapore
The one-cop-moves game on planar graphs

The one-cop-moves game on planar graphs

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 :

05 Sep 2019
17:00
S17 #06-11

Samuel Alfaro Tanuwijaya

Pseudo-finite fields

Pseudo-finite fields

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 :

29 Aug 2019
17:00
S17 #06-11

Chong Chi Tat
National University of Singapore
Revisiting Seetapun’s theorem with his disjunction

Revisiting Seetapun’s theorem with his disjunction

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 :

22 Aug 2019
17:00
S17 #06-11

Johanna Franklin

Degrees of isometric isomorphism for Banach spaces

Degrees of isometric isomorphism for Banach spaces

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 :