|
|
|
|
|
|
|
|
See by year | See by month | Jump to month | |
|
Ágnes Szendrei (University of Colorado, Boulder): Introduction to the Subpower Membership Problem - Part 2 |
|
|
|
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