The Subpower Membership Problem for a fixed finite algebra A (SMP(A)) is a combinatorial decision problem which asks, given a set of generators a_1,...,a_n and a distinguished tuple b in a direct power of A, is b in the subalgebra generated by a_1,...,a_n? In this talk, we discuss a construction which begins with any finite algebra A, and ends with a structurally 'nicer' algebra B for which SMP(B) is at least as hard as SMP(A). Given a specific finite algebra A, it is then natural to ask if the complexity of the associated problem SMP(B) is equal to or harder than SMP(A). We will look at a known example of a finite semigroup S for which SMP(S) is NP-complete, and show that the subpower membership problem for the associated 'nicer' algebra is also NP-complete.
An NP-Complete Example for the Subpower Membership Problem
Dec. 05, 2017 2pm (MATH 350)
Lie Theory
Josh Grochow (CU)
X
How hard it is to multiply matrices is a central open question in computational complexity, with ties to algebraic geometry and representation theory. In this talk I'll survey some recent work on matrix multiplication which brings together algorithms, representation theory, and additive combinatorics. Highlights include a transparent proof (joint with C. Moore) of Strassen's original 1969 algorithm for matrix multiplication - which was the first to beat steps - and using ideas from the resolution of the Cap Set Conjecture to deepen our understanding of the Cohn-Umans group-theoretic approach to matrix multiplication (joint with J. Blasiak, T. Church, H. Cohn, E. Naslund, W. F. Sawin, and C. Umans).
Representation theory and additive combinatorics in algorithms for matrix multiplication
Dec. 05, 2017 2pm (MATH 220)
Trevor Jack (CU Boulder)
X
A semigroup S is nilpotent if S^n = 0 for some n. We describe a polynomial-time algorithm for determining whether a semigroup of transformations given by generators is nilpotent.
Checking nilpotence for semigroups
Dec. 05, 2017 3pm (MATH 350)
Topology
Nikki Sanderson
X
Time series analysis traditionally relies upon statistics and frequency analyses that make restrictive assumptions about the data - i.e. nonlinearity, non-stationarity. We believe topological data analysis (TDA) can be of benefit in these situations. The process of delay coordinate reconstruction ``unfolds” a scalar time-series into a point cloud in Rm. We can then compute the persistent homology of the reconstructed data to obtain a topological signature. With the ultimate goal of regime shift detection in mind, we choose to use the witness complex - a sparse simplicial complex - for these computations. Topologically accurate delay reconstruction requires appropriate choices for the dimension m and time delay. We introduce novel witness relations that incorporate time and improve the robustness of the resulting homology with respect to choice of delay. The new relations seek to inhibit data points from witnessing landmarks traveling in dissimilar directions, as these can create false connections. We explore how these relations can ameliorate additional challenges that arise when dealing with nonuniform samples of strange attractors.
An NP-Complete Example for the Subpower Membership Problem