







See by year  See by month  Jump to month  

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



Wednesday, 22. September 2021, 10:00  12:00


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 © 20062013