Tyler Schrock On the complexity of isomorphism in finite group theory and symbolic dynamics
Thu, Oct. 31 2pm (MATH 350)
Functional Analysis
Paul Baum (Penn State University) ATIYAH-SINGER AS A COROLLARY OF BOTT PERIODICITY : PART 2 Sponsored by the Simons Foundation
Thu, Oct. 31 3pm (MATH 350)
Probability
Mei Yin (University of Denver) Perspectives on exponential random graphs
X
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.
X
This talk will take the outline provided in Part 1 and fill in details so as to provide a complete proof.
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.