Abstract:
The goal of this talk is to describe some interesting and elegant
mathematical questions that arise from computationally-motivated
questions. A subsidiary goal is to help break down the somewhat
artificial boundary in the continuum from computer science to computation
to mathematics. The talk will be organized around the following two
fundamental questions:
- Given generators for a permutation group, G < Sn, and
a group element g in Sn, how can one efficiently
decide if g belongs to G?
- Given generators for a permutation group, G < Sn,
how can one efficiently find generators for a normal subgroup of G or decide
that G is simple (has no normal subgroups)?
The talk requires as background only the definition of a group, of
a permutation group, and of Sn (the symmetric group
acting on n points).
The computer science notions of complexity and O(.) are also avoided.
While those notions are trivial, they are of a bookkeeping nature and
distract from the elegance of the underlying mathematical ideas.
|
alexsuciu@neu.edu