Overview
Date: October 14, 2023
Place: Wellesley College – All talks in Science Center N321
Schedule
| 10am | Coffee, Tea & Snacks |
| 10:15am | Caleb Camrud (Brown University) |
| 11:20am | Gihanee Senadheera (Winthrop College) |
| 12:20pm | Lunch |
| 2pm | Alex van Abel (Wesleyan University) |
| 3:05pm | Neil Lutz (Swarthmore College) |
| 4pm | End of day |
Speakers
Alex van Abel (Wesleyan University)
Asymptotics of the Spencer-Shelah Random Graph Sequence
In combinatorics, the Spencer-Shelah random graph sequence is a variation on the independent-edge random graph model. We fix an irrational number a in (0,1), and we probabilistically generate the n-th Spencer-Shelah graph (with parameter a) by taking n vertices, and for every pair of distinct vertices, deciding whether they are connected with a biased coin flip, with success probability n^{-a}. On the other hand, in model theory, an R-mac is a class of finite structures, where the cardinalities of definable subsets are particularly well-behaved. In this talk, we will introduce the notion of “probabalistic R-mac” and present an incomplete proof that the Spencer Shelah random graph sequence is an example of one.
Caleb Camrud (Brown University)
Computable Structure Theory of Continuous Logic
The primary models of continuous logic are metric structures. Due to their continuous nature, special care is required to translate and modify results given in classical computable structure theory to the metric setting of computable structure theory. In this talk, I will briefly introduce how effectivity is studied relative to continuous logic, and summarize three results from my dissertation in mathematics at Iowa State University: (1) a generalized effective completeness theorem for continuous logic and computable presentations, (2) the existence of numerals for hyperarithmetical real numbers coded by computable infinitary sentences, and (3) upper and lower bounds on the complexity of the various diagram levels of the finitary and infinitary theories of a computably presented metric structure. Result (2) is joint work with Timothy H. McNicholl, and result (3) is joint work with Timothy H. McNicholl and Isaac Goldbring.
Neil Lutz (Swarthmore College)
Applying Algorithmic Dimensions to Classical Problems
The point-to-set principle uses oracles to establish a tight connection between effective notions of fractal dimension and standard Hausdorff and packing dimensions. This connection allows algorithmic information techniques to be applied to problems in geometric measure theory. I will describe some of these applications as well as recent extensions of the point-to-set principle.
Gihanee Senadheera (Winthrop College)
Incomparable Degrees in PACi and PAC Learning
In 1984 Leslie Valiant introduced the Probably Approximately Correct (PAC) learning model, a machine learning model. To understand the learnability of the PAC model, whether it is linear or nonlinear we use the PAC reducibility and its degree structure. In 2018 Calvert introduced PACi reducibility where i stands for the definition being independent of size and time computation. This reducibility resembles Turing reducibility thus we can define PAC and PACi degrees. If incomparable degrees exist, then there are at least two different ways of non-learnability. To show that there are incomparable degrees we recursively construct two effective concept classes with PACi incomparable degrees using priority construction. A similar construction for PAC incomparable degrees as well. We apply Kolmogorov complexity to calculate the size of an effective concept class, as it is used in PAC reducibility. To approach a definition of jump operator we considered join of all the effective concept classes.
Travel Support
Limited funding is provided from the NSF to support participation by students and others to NERDS. If interested, please email Russell Miller.