CCS 2017 Programme

	5 January	6 January	7 January		8 January
9:00-10:00	Hirschfeldt	Chen	Jockusch	9:00-9:40	Slaman
10:00-10:40	Ng	Patey	Wu	9:40-10:20	McInerney
	Coffee break				Coffee break
11:00-11:40	Allender	Lempp	Nies	10:40-11:20	Shore
11:40-12:20	Cholak	Yu	Chong
	Lunch break
14:00-14:40	Ambos-Spies	Miller	Harizanov
14:40-15:20	Franklin	Morozov	Turetsky
	Coffee break
15:40-16:20	Melnikov	Schupp	Montalban
16:20-17:00		Gaspers

Abstracts

Eric Allender
The Complexity of Complexity (Slides)

There are many deep and surprising connections between computational complexity theory and various (computable and non-computable) measures of the "complexity" of a string. This talk will survey some of these connections, and will also discuss some recent developments concerning time-bounded Kolmogorov complexity and the "Minimum Circuit Size Problem".

---

Klaus Ambos-Spies
Array Noncomputable Left-c.e. Reals

We present some recent joint work with Nan Fang, Nadine Losert, Wolfgang Merkle, and Martin Monath on the array noncomputable (anc) and not totally ω-c.e. computably enumerable degrees, focussing on properties of left-c.e. reals. In particular, we discuss some obstacle for extending the notion of an anc set from the c.e. sets to the left-c.e. reals and we show how this obstacle can be overcome. Moreover, we show that - in contrast to the c.e. case - there are left-c.e. reals which are F-a.n.c. (in the stronger left-c.e. sense) for all very strong arrays. In fact we show that the Turing degrees of the left c.e. reals with this universal similarity property are just the c.e. degrees which are not totally ω-c.e.

We apply our new notions by showing that the Turing degrees of the left-c.e. reals which cannot be cl-reduced
to any complex left-c.e. reals are just the not totally ω-c.e. c.e. degrees. Moreover we show how our new notions can be used to give simplified proofs of some results in the literature, e.g., some of the results in Barmpalias, Downey and Greenberg (2010).

---

Yijia Chen
Domination Without Independence, a Tale of Parameterized Inapproximability (Slides)

Parameterized approximation is a combination of parameterized algorithms and classical polynomial time approximations. Its goal is to understand whether those hard parameterized problems can be fixed-parameter approximated. Rod et al initiated this subarea of parameter complexity in 2006. With his coauthors, in 2008 Rod provided the first graph-theoretic problem with no fpt-approximation of any approximation ratio. More precisely, it was shown that any fpt-approximation of the independent dominating set problem is W[2]-hard. It was left open whether a similar result holds for the (plain) dominating set problem. Partially answering this question, we show that any fpt-approximation of the dominating problem with constant approximation ratio is W[1]-hard. Interestingly, our hardness proof is built on the resolution of another major open problem in parameterized complexity, namely the W[1]-hardness of the biclique problem [Lin, 2015].

From a classical complexity perspective, our result yields a proof without the PCP machinery that the classical dominating set problem has no polynomial time constant approximation under the Exponential Time Hypothesis.

This is joint work with Bingkai Lin.

---

Peter Cholak
(Some) Lowness Notions in the c.e. Sets (Slides)

In the late 70's Soare showed the collection of all c.e. sets which contain a fixed low c.e. set A under inclusion are isomorphic to the collection of all c.e. sets under inclusion. In this talk we will explore the lowness notions needed for this result and a few recent related results.

---

Chi Tat Chong
1-Generic Degrees Bounding Minimal Degrees (Slides)

The existence of a 1-genetic degree bounding a minimal degree was previously shown by Chong and Downey, and Kumabe independently. In this talk we discuss the proof-theoretic strength of this problem in the context of reverse mathematics.

---

Johanna Franklin
Lowness in Computable Structure Theory

Lowness has been studied in the context of many different areas in computability theory, most prominently in classical degree theory and randomness. Solomon and I introduced lowness into computable structure theory with the concept of lowness for isomorphism, and Csima later introduced lowness for categoricity. I will give an overview of these results and then present some preliminary work concerning a new notion, lowness for isometry, that is joint with McNicholl.

---

Serge Gaspers
The Parameterized Complexity of Positional Games

In a positional game, two players alternately claim vertices of a hypergraph, and the winning configurations are described by the hyperedges. In a Maker-Maker game, the first player to have picked all the vertices of some hyperedge wins the game. In a Maker-Breaker game, the first player wins if she picks all the vertices of some hyperedge and the second player wins otherwise. In an Enforcer-Avoider game, the first player wins if the second player picks all the vertices of some hyperedge. For parameter k, we study the computational problem whether the first player can win the game in k moves from some given starting configuration against every strategy of the second player.

For concrete games, the hyperedges are often described implicitly. Generalized HEX, for example, is a Maker-Breaker game played on a graph with two distinguished vertices s and t, and the winning configurations are all the s-t-paths. The parameterized complexity of Generalized HEX was asked in Downey and Fellows' influential list of open problems from 1999. Whereas it was believed to be a natural candidate for AW[*]-completeness, we show that it is, in fact, complete for W[1].

Our main tool is a new fragment of first-order logic where universally quantified variables do not occur in inequalities. We show that model-checking on arbitrary relational structures for a formula in this fragment is W[1]-complete when parameterized by formula size.

In general, Maker-Maker games turn out to be AW[*]-complete, Maker-Breaker games W[1]-complete, and Enforcer-Avoider games coW[1]-complete. This suggests a rough parameterized complexity categorization into W[1]-complete positional games when the winning configurations only depend on which vertices player 1 has been able to pick, but AW[*]-completeness when the winning condition depends on which vertices both players have picked. However, some positional games where the board and the winning configurations are highly structured are fixed-parameter tractable. We give another example of such a game, Connect, which is fixed-parameter tractable when parameterized by the number of moves.

---

Valentina Harizanov
Orders on Computable Structures (Slides)

We study computability-theoretic and topological properties of right orders, left orders, and bi-orders on orderable magmas. A magma is an algebraic structure with a single binary operation. A magma is right-orderable if there is a linear ordering of its domain, which is right-invariant with respect to the operation. If the ordering is also left-invariant, then a magma is bi-orderable. Interesting magmas with a self-distributive operation that is not necessarily associative, which are right-orderable, come from knot theory and are called quandles. There is a natural topology on the set of all right (left) orders or bi-orders of orderable magmas. These spaces are compact, and for some well-known groups, they are homeomorphic to the Cantor set. Downey and Kurtz showed that a computable orderable abelian group does not necessarily have a computable order. Hence the space of orders of this group is homeomorphic to the Cantor set. For a large class of orderable residually nilpotent groups including surface groups, we investigate Turing degrees of their orders.

---

Denis Hirschfeldt
Some Questions in Computable Mathematics (Slides)

"Problems underpin what I do..." -- Rod Downey (from a personal history posted on his webpage)

Rod's research has spanned virtually all major areas of computability theory (and beyond). I have had the pleasure of working with him in algorithmic randomness and genericity, reverse mathematics, and computable structure theory. In this talk, based on a paper to be published in the Festschrift volume in his honor, I will discuss a few longstanding open questions related to our joint work.

---

Carl Jockusch
Imperfect Computability and Asymptotic Density (Slides)

I will discuss two notions of imperfect computability. One is generic computability, where an algorithm may never give an incorrect answer and must answer with (asymptotic) density 1. Another is coarse computability, where algorithms must always answer and must be correct with density 1. Topics include the interaction of these notions with Turing degrees, versions of these notions at lower densities, reducibilities associated with these notions, and interactions of these notions with algorithmic randomness. This will be a survey talk discussing the work of several researchers in an area that has been active in recent years.

---

Steffen Lempp
Nondensity of Double Bubbles in the d.c.e. Degrees (Slides)

Abstract:
In this talk, I will show that the so-called ``double bubbles'' are not downward dense in the d.c.e. degrees. Here, a pair of d.c.e. degrees e > d > 0 forms a “double bubble” if all d.c.e. degrees below e are comparable with d.

---

Michael McInerney
Multiple Genericity (Slides)

We introduce a hierarchy of genericity notions between 1-genericity and 2-genericity. We investigate the interaction between these notions and some domination properties related to Downey and Greenberg's hierarchy of totally α-c.a. degrees. Downward density of these generics holds at some levels of the hierarchy, but fails at others. We separate each of these notions in degree. This is joint work with Selwyn Ng.

---

Alexander Melnikov
Torsion-Free Abelian Groups with Optimal Scott Families (Slides)

We will discuss my recent solution to a problem of Goncharov on Delta_alpha-categorical TFAG (to be specified). This work is technically related to our joint work with Rod.

---

Antonio Montalban
Many-one Degrees with Names Like John or Paul

Abstract: We prove a version of the uniform Martin's conjecture for functions from Turing degrees to many-one degrees. We will talk about some other somewhat connected new results on topics like Fraisse's conjecture and analytic equivalence relations.
The part on many-one degrees is joint with Kihara and Slaman.

---

Joseph Miller
Generic Muchnik reducibility (Slides)

If A and B are countable structures, then A is Muchnik reducible to B if every ω-copy of B computes an ω-copy of A. This can be interpreted as saying that B is intrinsically at least as complicated as A. While this is a natural way to compare the complexity of structures, it was limited to the countable setting until Schweber introduced an extension to arbitrary structures: if A and B are (possibly uncountable) structures, then A is generically Muchnik reducible to B if in some (equivalently, any) forcing extension that makes A and B countable, A is Muchnik reducible to B.

I will review what is known about the generic Muchnik degrees and then discuss recent work with with Andrews, Schweber, and Soskova. We have proved the existence of a structure with degree strictly between Cantor space and Baire space. It remains open whether an expansion of Cantor space can be strictly in between, but we have proved that no closed expansion or unary expansion can work. Similar results hold for the interval between Baire space and the Borel complete degree (i.e., the degree that bounds all Borel structures). The proofs mix descriptive set theory (including some use of determinacy) with injury and forcing constructions native to computable model theory.

---

Andrey Morozov
On Σ-Presentability of Some Structures of Analysis over Hereditarily Finite Superstructures (Slides)

We study the simple Σ-presentability of some popular classical uncountable structures related to analysis in hereditarily finite superstructures over the existentially Steinitz structures, in particular, over the ordered field R of the real numbers.

Two general metatheorems are obtained which imply that there are no such simple presentations for a wide class of structures: in particular, for a series of automorphism groups, semigroups of continuous functions, some nonstandard extensions of R, etc.

Some open problems are discussed.

---

Keng Meng Ng
Automorphisms of Computable Linear Orders (Slides)

While the computable categoricity of linear orders has been completely described, it is of interest to study which (computable) linear orders are "rigid".

We discuss a recent solution to Kierstead's conjecture regarding automorphisms of computable linear orders. This is joint work with Maxim Zubkov.

---

Andre Nies
My Work with Rod 1995-2001 (Slides)

I will discuss results on degree structures obtained with Rod during the time 1995-2001. We worked on the Q-degrees of c.e. sets (with La Forte), polynomial time degrees, and the Solovay degrees of left-c.e. reals (with Hirschfeldt). The last direction paved the way for the later combination of randomness and computability.

---

Ludovic Patey
The Reverse Mathematics of Non-decreasing Subsequences (Slides)

Every function over the natural numbers has an infinite subdomain on which the function is non-decreasing. Motivated by a question of Dzhafarov and Schweber, we study the reverse mathematics of variants of this statement. It turns out that this statement restricted to computably bounded functions is an arguably natural principle between the arithmetic comprehension axiom and stable Ramsey’s theorem for pairs.

---

Paul Schupp
Geometric Group Theory, Genericity and Computability (Slides)

I will sketch why geometric group theory naturally led to generic-case complexity and computability and its viewpoint on the “coarsification” of computability.

---

Richard A. Shore
Conservativity of Ultrafilters over Subsystems of Second Order Arithmetic (Slides)

Ultrafilters have been very useful in proving (in ZFC or some extension of ZFC) combinatorial theorems stated in second order arithmetic. One would like an approach to converting the proofs into ones in some subsystem of second order arithmetic. We follow Towsner in proving conservation results over typical subsystems for the existence of various ultrafilters. Our approach uses forcing but the analysis is semantic rather than proof theoretic and gives some stronger results.

This is joint work with Antonio Montalban.

---

Ted Slaman
Irrationality Exponents and Effective Hausdorff Dimension (Slides)

With will discuss joint work with Verónica Becher and Jan Reimann. We generalize the classical theorem by Jarnik and Besicovitch on the irrationality exponents of real numbers and Hausdorff dimension. We show that there is a Cantor-like set with Hausdorff dimension equal to b such that, with respect to its uniform measure, almost all real numbers have irrationality exponent equal to a. Let a be any real number greater than or equal to 2 and let b be any non-negative real less than or equal to 2/a. We give an analogous result relating the irrationality exponent and the effective Hausdorff dimension of individual real numbers. We prove that there is a Cantor-like set such that, with respect to its uniform measure, almost all elements in the set have effective Hausdorff dimension equal to b and irrationality exponent equal to a. In each case, we obtain the desired set as a distinguished path in a tree of Cantor sets.

---

Dan Turetsky
TBA

TBA

---

Guohua Wu
There are no Maximal d.c.e. wtt-degrees (Slides)

We will talk about wtt-degrees of c.e. sets and d.c.e. sets, including some recent results on bounded jumps. Nonexistence of maximal d.c.e. wtt-degrees will be proved, and we will then talk about how to improve it to show the density of d.c.e. wtt-degrees.

---

Liang Yu
On the Reals Never Continuous Random (Slides)

Abstract: We investigate which reals can never be L-random. That is to give a description of the reals which are always belong to some L[λ]-null set for any continuous measure λ. Among other things, we prove that $NCR_L$ is an L-cofinal subset of $Q_3$ under ZFC+PD. This is joint work with Yizheng Zhu.

---

Back to CCS 2017 Main Page