See by year See by month Jump to month

Ágnes Szendrei (University of Colorado, Boulder): Introduction to the Subpower Membership Problem - Part 2

Download as iCal file
Friday, 24. September 2021, 10:15 - 12:15
Abstract. Let A be a fixed finite algebra with finitely many basic operations. The Subpower Membership Problem for A is the following combinatorial decision problem SMP(A):
Input: k+1 elements a_1, … , a_k, b of A^n (for some integers k,n>0).
Question: Is b in the subalgebra of A^n generated by a_1, … , a_k?

In the talks I plan to survey what is currently known about this problem, emphasizing how purely algebraic results have contributed to making progress. The outline is as follows:

1. The naive algorithm; applications of more efficient algorithms.
2. An efficient algorithm for classical structures (groups, rings, modules).
3. The largest class of algebras for which a similar `generalized Gaussian elimination’
algorithm might work: forks, few subpowers, edge/parallelogram terms.
4. A sufficient condition for a finite algebra A with a parallelogram term so that there
exists an efficient algorithm for SMP(A).
5. Next steps?
Location : Riesz Lecture Hall, 1st Floor, Bolyai Institute, Aradi Vértanúk tere 1., Szeged

Back

JEvents v3.1.8 Stable   Copyright © 2006-2013