Iowa State University logic and computability seminar calendar

The seminar will be held from 12:30 - 1:30 pm on Fridays in Carver 282. It is organized by Peter Burton; email me at pburton@iastate.edu to be added to the announcement mailing list.

Current calendar (will be updated periodically during semester)

• January 26: for this week only, the seminar will be held from 12:00 pm - 1:00 pm instead of the usual time.

  • Speaker: Peter Burton, Iowa State

  • Title: Hyperlinearity, soficity and Furstenberg’s x2 x3 conjecture (joint work with Maksym Chaudhary and Kate Juschenko)

  • Abstract: Furstenberg’s x2 x3 conjecture is a well-known problem in ergodic theory which asserts that normalized Lebesgue measure is the only diffuse probability measure on the unit circle invariant under the maps z -> z^2 and z -> z^3. In this talk, we will discuss an approach to this conjecture which relies on the theory of approximations to discrete groups, in particular a certain semidirect product Z^2 rtimes Z[1/6]. More specifically, we will explain how Furstenberg’s conjecture would follow from a strengthening of a previously established result of the speaker and coauthors connecting hyperlinearity and soficity.

• February 2:

  • Speaker: Peter Burton, Iowa State

  • Title: Hyperlinearity, soficity and Furstenberg’s x2 x3 conjecture, Part II (joint work with Maksym Chaudhary and Kate Juschenko)

  • Abstract: This seminar will be a continuation of the talk from January 26.

Previous calendar (Fall 2023)

• September 6: 

  • Speaker: Omer Tamuz, Caltech

  • Title: On the origin of the Boltzmann distribution (joint work with Fedor Sandomirskiy, Princeton)

  • Abstract: The Boltzmann distribution is used in statistical mechanics to describe the distribution of states in systems with a given temperature. We give a novel characterization of this distribution as the unique one satisfying independence for uncoupled systems. The theorem boils down to a statement about symmetries of the convolution semigroup of finitely supported probability measures on the natural numbers, or, alternatively, about symmetries of the multiplicative semigroup of polynomials with non-negative coefficients.

• September 13:

  • Speaker: Tim McNicholl, Iowa State

  • Title: Computing the unit

  • Abstract: Fix a commutative unital Banach algebra A.  An operation on A is intrinsically computable if it is computable referent to any presentation of A.  By definition, the multiplication, addition, and scalar multiplication operations of A are intrinsically computable.  We first show that the unit of A is intrinsically computable.  (We regard constants as 0-ary operations.)  We show that the unit of A can be computed from any presentation of A.  However, the proof is not uniform.  That is, different presentations yield different algorithms for computing the unit.  We then present several consequences of this result, concluding with the intrinsic computability of the involution, absolute value, maximum, and minimum operations.  

• September 27:

  • Speaker: Maksym Chaudhary, University of South Florida

  • Title: Hyperlinear approximations to amenable groups are induced by sofic approximations

  • Abstract: A discrete group is called sofic or hyperlinear if it admits metric approximations by finite permutation groups or by unitary groups of finite dimensional Hilbert spaces, respectively. It is well-known that every sofic group is also hyperlinear, and moreover, the class of sofic groups includes all amenable and all residually finite groups. In this talk we will describe the relationship between sofic and hyperlinear approximations for torsion-free amenable groups.  The talk is based on a joint work with Peter Burton, Kate Juschenko and Kyrylo Muliarchyk

• October 4:

  • Speaker: Laura Gamboa Guzman and Zili Wang, Iowa State

  • Mission-time Linear Temporal Logic (MLTL) is a crucial and practical fragment of Metric Temporal Logic. This logic mirrors the widely adopted Linear Temporal Logic (LTL) but integrates finite closed-interval integer bounds. Numerous tools are being developed to reason over MLTL specifications, but more tools must be needed to help system designers validate MLTL specifications. This talk will delve into our innovative approach to automating this validation. We've developed a sound and complete characterization of the computational structures that satisfy an MLTL formula based on regular expressions. We will present the theoretical underpinnings, introduce an algorithm for automated MLTL formula validation, and share insights into its theoretical and practical complexity. We have developed a comprehensive test suite anchored in control flow diagrams to ensure our system's robustness. As a testament to our commitment to the broader research community, we're pleased to announce the release of an open-source tool with an intuitive graphical interface. This tool enhances the existing algorithms for MLTL analysis and holds potential for broad-scale applications in various automated MLTL formula validation tools. In a highlight segment of our presentation, attendees will be treated to a live demonstration of our tool in action. This hands-on showcase will provide insights into the tool's user-friendly graphical interface, seamless formula validation process, and utility in real-world scenarios.

• November 1:

  • Speaker: James Anderson, Georgia Tech

  • Title: Borel line graphs

  • Abstract: We characterize Borel line graphs in terms of 10 forbidden induced subgraphs, namely the 9 finite graphs from the classical result of Beineke together with a 10th infinite graph associated to the equivalence relation $\E_0$ on the Cantor space. As a corollary, we prove a partial converse to the Feldman--Moore theorem, which allows us to characterize all locally countable Borel line graphs in terms of their Borel chromatic numbers.

• November 8:

  • Speaker: Anton Bernshteyn, Georgia Tech (joint work with Jing Yu)

  • Title: Large-scale geometry of Borel graphs of polynomial growth

  • Abstract: Krauthgamer and Lee showed that every connected graph of polynomial growth admits an injective contraction mapping to $(\mathbb{Z}^n, \|\cdot\|_\infty)$ for some $n \in \mathbb{N}$. We strengthen and generalize this result in a number of ways. In particular, answering a question of Papasoglu, we construct coarse embeddings from graphs of polynomial growth to $\mathbb{Z}^n$. Furthermore, we extend these results to Borel graphs. Namely, we show that graphs generated by free Borel actions of $\mathbb{Z}^n$ are in a certain sense universal for the class of Borel graphs of polynomial growth. This provides a general method for extending results about $\mathbb{Z}^n$-actions to all Borel graphs of polynomial growth. For example, an immediate consequence of our main result is that all Borel graphs of polynomial growth are hyperfinite, which answers a well-known question in the area. An important tool in our arguments is the notion of Borel asymptotic dimension.

• December 13:

  • Speaker: Clinton Conley, Carnegie Mellon (joint work with Jackson, Marks, Seward, and Tucker-Drob)

  • Title: Borel asymptotic dimension and hyperfiniteness

  • Abstract: Borel asymptotic dimension and hyperfiniteness We introduce a “purely Borel” version of Gromov’s notion of asymptotic dimension, and show how to use it to establish hyperfiniteness of various equivalence relations. Time permitting, we discuss hyperfiniteness of orbit equivalence relations of free actions of lamplighter groups and groups with similar geometry.