Conjugacy is the natural notion of isomorphism in symbolic dynamics. A major open problem in the field is that of finding an algorithm to determine conjugacy of shifts of finite type (SFTs). We consider several related computational problems restricted to k-block codes. We show verifying a proposed k-block conjugacy is in P, finding a k-block conjugacy is GI-hard, reducing the representation size of a SFT via a 1-block conjugacy is NP-complete, and recognizing if a sofic shift is a SFT is in P.
Then we consider the complexity of isomorphism among finite groups, where we consider isomorphism between quotients of genus 2 groups. The centrally indecomposible genus 2 groups split into two cases: flat and sloped. We show determining isomorphism between quotients of genus 2 groups by non-central subgroups is in P and determining isomorphism between quotients of the genus 2 groups H^\flat_1 by central subgroups is in P.
On the complexity of isomorphism in finite group theory and symbolic dynamics
Oct. 31, 2019 2pm (MATH 350)
Functional Analysis
Paul Baum (Penn State University)
X
This talk will take the outline provided in Part 1 and fill in details so as to provide a complete proof.
ATIYAH-SINGER AS A COROLLARY OF BOTT PERIODICITY : PART 2 Sponsored by the Simons Foundation
Oct. 31, 2019 3pm (MATH 350)
Probability
Mei Yin (University of Denver)
X
Exponential random graphs are powerful in the study of modern networks. By representing a complex global configuration through a set of tractable local features, these models seek to capture a wide variety of common network tendencies. This talk will look into the asymptotic structure of weighted exponential random graphs and formulate a quantitative theory of phase transitions. The main techniques that we use are variants of statistical physics. Based on joint work with multiple collaborators.
On the complexity of isomorphism in finite group theory and symbolic dynamics