Logic seminar: Manabu Hagiwara @ Keller 303
Sep 15 @ 1:30 pm – Sep 15 @ 2:30 pm

I will give a tutorial talk, how to use LEAN and Coq/MathCopm.SSReflect, which are famous proof assistant systems.

Keller 303

Logic seminar: Mushfeq Khan
Sep 22 @ 1:30 pm – Sep 22 @ 2:30 pm

This week Mushfeq Khan is continuing his
seminar from 2 weeks ago on
“Turing degrees and Muchnik degrees of recursively bounded DNR functions”.


This talk is based on a forthcoming paper by Steve Simpson. It contains
some results that shed light on a part of the Muchnik lattice that remains
poorly understood: the various degrees of recursively bounded DNR functions
obtained by varying the recursive bound.

Keller Hall 303

Logic Seminar: William DeMeo @ Keller 303
Sep 29 @ 1:30 pm – Sep 29 @ 2:20 pm

TITLE: The Algebraic Approach to Determining the Complexity of Constraint Satisfaction Problems

SPEAKER: William DeMeo

ABSTRACT: The “CSP-dichotomy conjecture” of Feder and Vardi asserts that every constraint satisfaction problem (CSP) is in P or is NP-complete. Sometime around the late 1990′s it was observed that a CSP is naturally associated with a general (universal) algebra via a certain Galois connection, and that this connection makes it possible to use algebraic methods to determine the complexity class of a CSP. This led to the “algebraic CSP-dichotomy conjecture” which, after more than a decade of substantial research, has been reduced to the following conjecture: the CSP associated with a finite idempotent algebra A is tractable if and only if the variety generated by A has a Taylor term.

In this talk we try to give most of the background required to understand the algebraic approach to CSP. We give some concrete examples that demonstrate how one uses properties of a universal algebra to determine the complexity class of a CSP. If time permits, we will highlight some of our most recent discoveries that have helped resolve the dichotomy conjecture for most idempotent varieties.

The talk should be fairly self-contained for anyone greater than or equal to a math or cs graduate student. Roughly speaking, if you have heard of the complexity classes P and NP and if you know what a universal algebra is, then you should understand most of this talk.

Logic Seminar: David Ross @ Keller Hall 303
Oct 6 @ 1:30 pm – Oct 6 @ 2:30 pm

TITLE: Asymptotic Fixed Points, Part I.

ABSTRACT: By a standard exercise, a uniform contraction on a complete metric
space has a fixed point. Easy examples show that this fails if the
contraction is not uniform. I will discuss some recent results where the
uniform property is replaced by asymptotic conditions on the contraction.
These results are most easily framed and proved using methods from
nonstandard analysis, so I will also briefly brief review those methods. If
there is interest, I will actually prove some of the fixed-point results in
a second seminar (hence the “Part I.”)

André Nies: A gentle introduction to randomness and $K$-triviality
Oct 18 @ 1:30 pm – Oct 18 @ 2:20 pm

Keller 303
Introduction for grad students and other beginners, as a prequel to Thursday’s talk.

Logic Seminar: André Nies
Oct 20 @ 1:30 pm – Oct 20 @ 2:30 pm

Speaker: André Nies (University of Auckland), Fellow of the Royal Society of New Zealand

Title: Structure within the class of $K$-trivial sets

Abstract: The $K$-trivial sets are antirandom in the sense that the initial segment complexity in terms of prefix-free Kolmogorov complexity $K$ grows as slowly as possible. Since 2002, many alternative characterisations of this class have been found: properties such as low for $K$, low for Martin-Löf (ML) randomness, and basis for ML randomness, which state in one way or the other that the set is close to computable.

Initially the class looked quite amorphous. More recently, internal structure has been found. Bienvenu et al. (JEMS 2016) showed that there is a “smart” $K$-trivial set, in the sense that any ML-random computing it must compute all $K$-trivials. Greenberg, Miller and Nies (submitted) showed that there is a dense hierarchy of subclasses. Even more recent results with Turetsky combine the two approaches using cost functions.

The talk gives an overview and ends with open questions (of which there remain many).

Location: Keller Hall 303

Logic Seminar: David Ross part II
Oct 27 @ 1:30 pm – Oct 27 @ 2:30 pm

TITLE: Asymptotic Fixed Points, Part II

ABSTRACT: Continuing the earlier seminar, I will give nonstandard proofs for
one or more (depending on time) results like the
one below (which consolidates and generalizes a number of recent results in
the area).


$(X,d)$ is a complete metric space,

$T:Xto X$ is continuous,

$phi, phi_n:[0,infty)to[0,infty)$, and
$phi_n$ converges to $phi$ uniformly on the range of $d$,

$phi$ is semicontinuous and satisfies $phi(s)0$,

$d(T^nx,T^ny)lephi_n(d(x,y))$ for all $x,yin X$ and $ninmathbb N$.

Moreover, suppose that for any $x,y$, $phi(t)lesssim t$ on infinite
elements of
$${^*d(T^nx,T^my) : m, n text{ hyperintegers}}.$$
Then $T$ has a unique fixed point $x_infty$, and for every $xin X, limlimits_{ntoinfty}T^n(x)=x_infty$. Moreover, this convergence is
uniform on bounded subsets of $X$.

Logic seminar: Mushfeq Khan
Feb 10 @ 2:30 pm – 3:30 pm

The Sporadic Logic Seminar returns this week at a new place and time
(Fridays, 2:30, K404). This week Mushfeq Khan will speak:

Title: “The Homogeneity Conjecture”

Abstract: It is often said that the theorems and methods of recursion theory
relativize. One might go as far as to say that much of its analytical power
derives from this feature. However, this power is accompanied by definite
drawbacks: There are important examples of theorems and open questions
whose statements are non-relativizing, i.e., they have been shown to be
true relative to some oracles, and false relative to others. It follows
that these questions cannot be settled purely through relativizing methods.
A famous example of such a negative result is Baker, Gill, and Solovay’s
theorem on the P vs. NP question.

The observation that techniques based on diagonalization, effective
numbering, and simulation relativize led some recursion theorists (notably
Hartley Rogers, Jr) to formulate what became known as the “Homogeneity
Conjecture”. It said that for any Turing degree d, the partial order of
degrees that are above d is isomorphic to the entire partial order of the
Turing degrees. In 1979, Richard Shore refuted it in an elegant, one-page
article which will be the subject of this talk.