The 23rd Graduate Student Conference in Logic
April 15-16, 2023
University of Illinois at Chicago
The GSCL is a weekend conference organized by and for graduate students studying mathematical logic. This year’s conference will be held in-person at the University of Illinois at Chicago.
GSCL XXIII is generously supported by the Association for Symbolic Logic and the Institute for Data, Econometrics, Algorithms, and Learning. The special session on Logic, Algorithms, and Machine Learning is part of the IDEAL Winter/Spring 2023 Special Quarter on Machine Learning and Logic.
Organizers: Will Adkisson, Kevin Zhou
Special Session on Logic, Algorithms, and Machine Learning
Eben Blaisdell, University of Pennsylvania
Title: Substructural logic: an intersection of math, CS, linguistics, and philosophy
Abstract: Lambek (1958) introduced a restriction of Gentzen’s sequent calculus motivated by the syntax of natural language. Since then, many more so-called substructural logics have emerged, most famously Girard’s linear logic (1987). In this talk I present a friendly introduction to substructural logic, survey applications in algebra, CS, linguistics, and philosophy, and present recent work on the (un)decidability of interesting logics in this area.
Antonio Nakid Cordero, University of Wisconsin-Madison
Title: Algorithmic Content of Topological Spaces
Abstract: One of the goals of computability theory is to measure and classify the algorithmic content of mathematical objects. The classic tools used to compare computational strength are Turing reduction and its associated structure, the Turing degrees.
In this talk, we will discuss the enumeration degrees, a more general notion that allows us to compare the algorithmic content of some topological spaces. We will also explore how this connection can be exploited to study the intricate structure of subclasses of the enumeration degrees.
Gregoire Fournier, University of Illinois at Chicago
Title: TBA
Abstract: TBA
Ang Li, University of Wisconsin-Madison
Title: Introenumerability, Autoreducibility, and Randomness
Abstract: It’s known that the class of total enumeration degrees has measure zero. In this talk, we define $\Psi$-autoreducible sets given an autoreduction procedure $\Psi$. Then, we show that a measurable class of $\Psi$-autoreducible sets has measure zero for a fixed $\Psi$. Using this, we show that classes of cototal, uniformly introenumerable, introenumerable, and hyper-cototal enumeration degrees all have measure zero. Then, we discuss what level of randomness these e-degrees could have because sufficiently random sets must avoid such enumeration degrees.
Clark Lyons, University of California, Los Angeles
Title: Descriptive Combinatorics and Distributed Computing
Abstract: Given a graph labeling problem $P$, we can measure the complexity of solving it in many ways. In the LOCAL model of distributed computing we can measure this complexity by asking how many rounds of communication are required asymptotically to solve $P$ if the vertices all communicate with their neighbors and run the same local algorithm. And we can also ask whether there always exist measurable labelings that solve $P$ on graphs with a Borel structure. It turns out that these two measures of complexity have a deep relationship, whereby upper and lower bound results for the complexity of a problem can be translated from one side to the other. In this talk we will see how this connection motivates some new applications of determinacy to impossibility results for labeling problems, including the 1-star and 3-star cover problem and the hairy paths cover problem.
Luke MacLean, University of Waterloo
Title: An application of Antonio Montalban’s game metatheorem
Abstract: The majority of this talk will be spent explaining and singing the praises of the game metatheorem of Antonio Montalban. It is a combinatorial framework that allows one to carry out $\Delta^0_\alpha$ priority constructions in a much simpler fashion than other popular metatheorems such as the $\alpha$-systems of Ash & Knight. This is a much more intuitive approach to priority constructions which more than makes up for its slightly restricted range of applications as compared to an $\alpha$-system. Near the end I will talk about a recent application of the metatheorem that I have used to study the degree spectra of unary relations on linear orders.
Karthik Ravishankar, University of Wisconsin-Madison
Title: Isomorphisms between computable structures
Abstract: Given two computable copies of a structure, it is interesting to analyze the information encoded in an isomorphism between the two copies. Towards this end, we shall look at two dual notions: The least powerful degree which can compute an isomorphism while no computable isomorphism exists as well as the most powerful degree which is needed in general to compute an isomorphism between two computable copies.
Chris Shulz, University of Illinois Urbana-Champaign
Title: Definability and decidability for expansions of arithmetic by sets definable from positional numeration systems
Abstract: This talk is a summary of my doctoral dissertation. In it, we will establish several results in the study of the tameness of expansions of various forms of arithmetic. Here arithmetic roughly means the ordered additive structure of a familiar set of numbers, specifically as pertains to encodings of the elements of the structure. First, we will give a strong version of Cobham’s theorem on the k-automatic sets of integers, as well as demonstrating why the method of proof must be different from earlier results in this direction. Second, we will examine the fractal properties of k-automatic subsets of the unit box, giving procedures for their computation. Third, we will shift our attention from k-automaticity to sets defined from Ostrowski representation, which leads to a new method for automated theorem-proving in the study of Sturmian words.