Overview

Date: Saturday, April 7, 2018
Time: 10:30am-3:30pm
Place: University of Connecticut (Directions to campus)
Monteith Building (Campus map).
Parking: Unless explicitly marked as reserved, all lots are free on the weekends. In garages, regular rates apply. (Parking map)

Schedule

10:30–11a	Coffee and Pastries	MONT 201 (2nd Floor Lounge)
11a–12p	Jun Le Goh (Cornell University)	MONT 226
12–1p	Jennifer Chubb (University of San Francisco)	MONT 226
1–2:30p	Lunch
2:30–3:30p	Jan Reimann (Penn State University)	MONT 226

Abstracts

Jun Le Goh

Some reductions between theorems around ATR

We study theorems with reverse mathematical strength around ATR from the point of view of computability-theoretic reducibilities. Consider the ATR-like problem of producing the jump hierarchy on a given well-ordering. Consider also its “two-sided” version: given a linear ordering L, produce either a jump hierarchy on L or an infinite L-descending sequence. We present reductions between these problems and weak comparability of well-orderings, the restriction of Fraisse’s conjecture to well-orderings, and Koenig’s duality theorem. In particular, we answer a question of Marcone by showing that comparability of well-orderings is Weihrauch equivalent to its weak version.

Jennifer Chubb

Detecting properties from descriptions of groups

The complexity of the word, conjugacy, and isomorphism problems of finitely presented groups have long been of interest in combinatorial group theory, logic, and algebra in general. Motivating questions are whether (and ideally, how) the presentation of a group in terms of generators and relators can shed any light on the existence of algorithms that solve these problems, or whether the groups exhibit other properties of interest. These questions are usually formulated as what we’ll call detection problems, questions of the form “Does presentation D yield a group which exhibits property P?”

We consider detection problems in two classes of descriptions of groups. The first is the class of recursive presentations of groups, in which we are given an algorithm that identifies the generators and relators in the presentation. The second is from the point of view of computable structure theory, from which we consider another type of algorithmic description of a group, its computable atomic diagram.

From either perspective we are asking whether, given a simple, finite description of a group in the form of an algorithm, it is possible to effectively determine whether or not the group has some specified property. When there is such an effective procedure, we say the property is recursively recognizable within some class of descriptions. When there is not, we ask how algorithmically complex detection would be.

We were originally motivated by a desire to determine from a recursive presentation or atomic diagram whether or not a group is orderable. While we see results in that context, we will begin by considering a much more general class of properties, Markov properties, which include having a solvable word problem, being torsion-free, trivial, nilpotent, abelian, orderable, etc. We will see precise characterizations of the algorithmic complexity of the detection problems for many of these properties.

This work is joint with Iva Bilanovic and Sam Roven.

Jan Reimann

Kolmogorov Complexity and Diophantine Approximation

Diophantine approximation asks for the best approximation of a real number by rationals (relative to the size of the denominator). The basic paradigm has many similarities with Kolmogorov complexity, in fact, it can be seen as a version of complexity with very limited computational power. I will illustrate these similarities with the help of two classic results in Diophantine approximation: the Jarnik-Besicovitch theorem in metric Diophantine approximation and Thue’s theorem on approximation of algebraic numbers.