Archives of: NUS logic seminar

Konstantin Slutsky: Orbit equivalences of Borel flows

Invitation to the Logic Seminar at the National University of Singapore

Date: Wednesday, 14 November 2018, 17:00 hrs

Room: S17#04-05, Department of Mathematics, NUS

Speaker: Konstantin Slutsky

Title: Orbit equivalences of Borel flows

URL: http://www.comp.nus.edu.sg/~fstephan/logicseminar.html

Abstract:
The purpose of this talk is to provide an overview of the orbit
equivalence theory of Borel R^n-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^n-flows taking the viewpoint of Borel dynamics.

For a free R^n-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^n
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^n actions.
We illustrate this by outlining a proof of the analog for
R^n-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.

George Barmpalias: Compression of data streams down to their information content

Invitation to the Logic Seminar at the National University of Singapore

Date: Wednesday, 7 November 2018, 17:00 hrs

Room: S17#04-05, Department of Mathematics, NUS

Speaker: George Barmpalias

Title: Compression of data streams down to their information content

URL: http://www.comp.nus.edu.sg/~fstephan/logicseminar.html

Abstract:
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.

Frank Stephan: A fast exponential time algorithm for Max Hamming Distance X3SAT

Invitation to the Logic Seminar at the National University of Singapore

Date: Wednesday, 24 October 2018, 17:00 hrs

Room: S17#04-05, Department of Mathematics, NUS

Speaker: Frank Stephan

Title: A fast exponential time algorithm for Max Hamming Distance X3SAT

URL: http://www.comp.nus.edu.sg/~fstephan/logicseminar.html

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
Wahlstroem from 2007 provides time O(1.0984^n).
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^n) and the contribution
of the here presented work is to bring this down to O(1.3298^n).

This is joint work with Gordon Hoi and the paper is available
from the speaker’s homepage.

Dilip Raghavan: Order dimension

Invitation to the Logic Seminar at the National University of Singapore

Date: Wednesday, 17 October 2018, 17:00 hrs

Room: S17#04-05, Department of Mathematics, NUS

Speaker: Dilip Raghavan

Title: Order dimension

URL: http://www.comp.nus.edu.sg/~fstephan/logicseminar.html

Abstract: 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.

Ashutosh Kumar: Saturated null and meager ideal

Invitation to the Logic Seminar at the National University of Singapore

Date: Wednesday, 19 September 2018, 17:00 hrs

Room: S17#04-05, Department of Mathematics, NUS

Speaker: Ashutosh Kumar

Title: Saturated null and meager ideal

Abstract: We will sketch some ideas behind the proof of the following:
The null and the meager ideal could both be somewhere countably
saturated.

Link for Paper: http://www.math.nus.edu.sg/~matak/snmi.pdf

Borisa Kuzeljevic: P-ideal dichotomy and some versions of the Souslin’s Hypothesis

Invitation to the Logic Seminar at the National University of Singapore

Date: Wednesday, 12 September 2018, 17:00 hrs

Room: S17#04-05, Department of Mathematics, NUS

Speaker: Borisa Kuzeljevic

Title: P-ideal dichotomy and some versions of the Souslin’s Hypothesis

URL: http://www.comp.nus.edu.sg/~fstephan/logicseminar.html

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 Todorcevic.

Frank Stephan: Computational aspects of the hyperimmune-free degrees

Invitation to the Logic Seminar at the National University of Singapore

Date: Wednesday, 15 August 2018, 17:00 hrs

Room: S17#04-05, Department of Mathematics, NUS

Speaker: Frank Stephan

Title: Computational aspects of the hyperimmune-free degrees

URL: http://www.comp.nus.edu.sg/~fstephan/logicseminar.html

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.

Samuel Alfaro Tanuwijaya: Introduction to surreal numbers

Invitation to the Logic Seminar at the National University of Singapore

Date: Wednesday, 18 April 2018, 17:00 hrs

Room: S17#04-06, Department of Mathematics, NUS

Speaker: Samuel Alfaro Tanuwijaya

Title: Introduction to surreal numbers

URL: http://www.comp.nus.edu.sg/~fstephan/logicseminar.html

In this talk, I will introduce the basic definitions of the surreal
numbers and their ordering given in the book by Harry Gonshor, and
their relations to the definitions given by Conway and Knuth. I will
then continue with the definitions operations on the numbers, such as
addition, multiplication, and division, and then prove that the
surreal numbers form a field. I will then establish that the surreal
numbers contain the real numbers and the ordinals.

David Chodounsky: How to kill a P-point

Invitation to the Logic Seminar at the National University of Singapore

Date: Wednesday, 14 March 2018, 17:00 hrs

Room: S17#04-06, Department of Mathematics, NUS

Speaker: David Chodounsky

Title: How to kill a P-point

URL: http://www.comp.nus.edu.sg/~fstephan/logicseminar.html

Abstract:
The existence of P-points (also called P-ultrafilters) is independent
of the axioms of set theory ZFC. I will present the basic ideas behind
a new and simple proof of the negative direction of this fact; a new
forcing method for destroying P-points.

Sibylle Schwarz: Many-valued logic, Automata and Languages

Invitation to the Logic Seminar at the National University of Singapore

Date: Wednesday, 21 February 2018, 17:00 hrs

Room: S17#04-06, Department of Mathematics, NUS

Speaker: Sibylle Schwarz

Title: Many-valued logic, Automata and Languages.

URL: http://www.comp.nus.edu.sg/~fstephan/logicseminar.html

Abstract:
In 1960, Buechi, Elgot, Trakhtenbrot discovered a correspondence
between finite automata and monadic second order logic on words:
A language of nonempty words is regular if and only if it is
MSO-definable. Many-valued logics with truth values from MV-algebras
and weighted automata with weights from semirings are generalizations
of classical two-valued logics and finite automata, respectively.
In this talk, I give some examples of corresponding MV-algebras
and semirings and present translations between many-valued
MSO-formulae and weighted automata that define the same language.