Recently, Bulin, Krokhin, and Oprsal have found sufficient conditions for NP-hardness of a promise constraint satisfaction problem (PCSP). Their method involves defining a new class of problems, the problems of deciding triviality of a set of minor identities, which can been viewed as an algebraic version of Label Cover problems. Every PCSP with a fixed constraint language is log-space equivalent to a promise version of these problems. We will discuss this equivalence as well as how these new problems provide sufficient conditions for NP-hardness of PCSPs.
NP-hardness of PCSPs (part 1)
Feb. 05, 2019 2pm (MATH 220)
Michael Wheeler (CU Boulder) p = t via Nonstandard Models of Set Theory, Part 2
Feb. 05, 2019 2pm (MATH 350)
Lie Theory
Nat Thiem (CU)
X
This semester the ALT seminar will give an introduction to Hopf algebras. We will begin with some survey talks, and also have some research talks later in the semester. This talk is the first such survey talk.
Hopf algebras crop up naturally throughout mathematics, and require numerous natural operations to harmonize. This introductory talk focuses on two strands of Hopf theory: Hopf algebras as a direct generalization of group theory and Hopf algebras as a repository for combinatorial gizmos. We will motivate the study Hopf algebras with the first approach and then proceed to show how the second perspective completely alters the paradigm. Throughout we will try to highlight some of the types of questions that arise and key examples.
Hopf structures in algebra and combinatorics
Feb. 05, 2019 4pm (MATH 350)
Topology
Agnes Beaudry (CU Boulder) Classifying spaces and tangential structures