*******************************************************************
Jelani

Wednesday's lecture forced me to do some algebra review (I haven't
touched abstract algebra for about 3 years), but it was good for me.
For instance, I had to rethink why every group is isomorphic to a
subgroup of S_{|G|}.  Speaking of which, algorithmically are there any
results to find the least n such that G is isomorphic to a subgroup of
S_n?

The lecture I found coordinated and not too confusing.  For a bit, I
was confused about why the strong generating set we were finding was
small (we only proved that a small one existed, but not that the one
we were finding was small), but after a student asked this to you in
class, your answer cleared up my confusion (the fact for every i,j
pair, we only pick one element that fixes everything above j and swaps
i to j).

*******************************************************************
Elena

I thought that the definition of SGSs is very non-intuitive. Namely, why would a
group G contain a \tau that fixes that last set of elts (besides id)? Or, if G
does not contain such a \tau what would a SGS be (by the definition)? Also, I
was wondering about the relative sizes of a minimal generating set and a
minimal SGS?
In the construction of a minimal SGS from S, if S is not minimal do we still get
a minimal SGS?

I think that we might have gone a bit too fast over the proofs, but I don't
think that we should go back and discuss them since the notes that you posted
were clarifying enough. Instead, I might like to get a bit more intuition into
why these SGSs are the 'core' of any permutation group. I was also wondering
what other applications besides membership testing do the SGSs have?

*******************************************************************
Michael M.

my main comment about wed's lecture is that, whenever something is
being defined, it would be nice to always get the precise definition
and not just the idea through pictures or examples.  the definition of
\bar T, e.g., only became clear to me when you wrote it out in full.
it would also be nice (and this is a more general comment) if you'd
spend a little time, after presenting each major algorithm or method,
summarizing how the technique was useful (if it was) in complexity,
crypto, etc...

*******************************************************************
Ben R. 

I had no trouble following Wednesday's lecture, perhaps because I have seen
Sims? algorithm before.  Last year I attempted to read the NC algorithm for
group membership due to Babai, Luks and Seress, which uses some nontrivial
permutation group theory (including the classification of finite simple
groups).  Strong generating sets are also important there, as they are in every
other group-theoretic algorithm I've looked at.

*******************************************************************
Brendan 

I thought Wednesday's lecture was extremely clear, especially compared to the
previous lecture (where, I confess, I couldn't follow the sketch of the proof
of Gauss' Lemma, etc. at all). I'm not sure what to attribute this to, but
possibilities include:

1) my algebra was rusty coming in and I spend the weekend reviewing
2) the arguments were provided in significantly more detail
3) the content was more algorithmic
4) the use of pictures?

I liked the content, but I don't feel any particular need for it to be reviewed
in lecture again (i.e., since I feel like I "got it") and I'd be happy to move
on to other topics on Monday and beyond.

*******************************************************************
Kyo-Min

The strong generating set was a nice middle structure that can be used to test

the required test(in this case, group membership test) in polynomial time.

The example of cubic game was helpful to understand the basic concept of strong

generating set. I became curious about the general case, where the base group

is not S_n but any group. If the given base group can be understood as an

action group on a set A where |A|=poly(n) where n is a complexity parameter,

then strong generating set argument is applied to obtain a poly time algorithm

for the group membership test.

But in other case, I think it cannot be applied. So it will be nice if we can

know some results or reference about other case.

I think the class was rather fast to understand the details of the proof in

the class.

*******************************************************************
Sophie

The goal of this lecture was to develop an approach for determining whether a given member of a group in the permutation group is a member of a subgroup generated by a set of elements. The method used is that similar to the approach to solving a Rubik's cube, that is, we successively fix larger and larger parts of the group. In the context of a group, we introduce the notion of a strong generating set (SGS) of a group. An SGS for a group contains, for every element t of G that leaves all elements larger than k fixed, with t(j)=k, an element satisfying those properties. 

We proved that given any subgroup G of S_n, it has a SGS of size O(n^2). We used the idea of the closure of a set, or the set of greedy right-to-left products of elements of T to do this. We note that the closure of an SGS is the whole generating set S, so we start out with T as the empty set, and then grow T until its closure is the whole set. We pick the elements by which we "grow" T by taking elements of the set T union S whose product is not in T closure, and adding some relative of the product to T. Finally, we prove that when we have that for all pairs of elements of T, their product is in the closure, T is an SGS for S. 

As far as comments about the lecture go - I appreciated the diagrams illustrating how the different permutations leave certain elements fixed - it made it much easier to understand the process by which we grew the SGS. It would have been good to at the end tie the SGS back to the original problem of a membership algorithm, since you didn't actually give a membership algorithm, and it would be nice to see the motivation for the notion of an SGS put to use. It seems that we can use the much smaller SGS T of S to determine if a given permutation is in the subgroup of S_n generated by S, but it is not immediately clear how to do this.

*******************************************************************
Eitan

I really enjoyed Thursday's lecture about membership in permutation groups.
The notion of a strong generating set was presented well using the rubik's
cube as an analogy.  The idea of the strong generating set elements
corresponding to moves that preserve part of our permutation and switch one
thing in a desired way was a natural way to approach the problem and made
the proofs follow intuitively.

One part that confused me a little was the distinction between the
membership problem and the proof that the entire group is generated by the
SGS.  While this was clarified soon after because they are intimately
related, it was the only part of the lecture that I found confusing.  This
was probably not anything wrong with the lecture and seems like it is just
something that I needed to work out in my head for a minute.  I don't think
we need to go over any parts of this lecture on Monday unless a significant
number of people are confused about it.  I look forward to the factorization
algorithms.

*******************************************************************
Karola

I liked the lecture, since the notion of the symmetric group is an
exciting topic, extensively studied in mathematics, so I was glad to
see a CS approach to it. I find that the goal of the lecture was clear at
all times. Also, the idea that we are trying to obtain a suitable
generating set for our subgroup of the permutation group was well
motivated.

I found the concept of a SGS certainly not obvious, but fully
comprehensible. However, I feel that I do not have sufficient intuition
for the definition of the closure of T (T-bar). Taking the definition
of T-bar for granted, the lecture flowed naturally, though
I would like to know a strict proof, for example for the last lemma
stated.

*******************************************************************
Krzyztof


The presented algorithm was an interesting example of some more general technique that
could be described by "find a good base and express whole space by it".That technique is
used in Gauss elimination method, and in at least a few other.

The algorithm was understandable, and it is not very complicated. Although the end of the
lecture was presented in a rush, and we only skimmed through the proofs, I don't think it
is worth coming back to it.

*******************************************************************
David S.

I'm primarily interested in the part of the course that "will focus on
the interplay between complexity theory and algebra as highlighted by
algebraic versions of the P vs. NP question", though I'm also looking
forward to seeing some of the algorithms for primality testing. I'm
not sure where you intend to go with Wednesday's lecture -- will this
give us insight into how to describe complexity classes using algebra?
Does the material have any real-world applicability?

*******************************************************************
Jingbin

In this lecture, we mainly talked about the way to specify a subgroup G of Sn by its
Strong Generating Set. We showed the two reason why SGS is much more useful than
the ordinary generation set in computation, that is SGS assures that not only the num-
ber of its elements but also the length of the sequence to generate a element in G are
both polynomial of n. And ¯nally, we constructed an algorithm to construct a SGS for
certain G whose running time is also polynomial time.
The lecture shows the power of SGS when specifying G. However, in math, we prefer
to generating set which has the minimum number of elements, so that we could have a
clear look of the structure of G. This contradicts to the real condition in computation.

*******************************************************************
Jinwoo

The contents of the lecture is the membership algorithm of S_n(the permutation
group) using a strong generating set. At first, we can test the membership test
in polynomial time of n. Secondly, we can find a strong generating set in
polynomial time of n.

The main idea is a strong generationg set, and it is a nice idea. But, although
the definition of the strong generating set is somewhat confusing at my first
time, I think it is a natural idea which someone can find intuitively. I think
there can be a better algorithm.

When we think the general group rather than S_n, it is hopeful because every
finite group is a subgroup of S_n. But, I don't know how to find S_n from the
general group. Also, I think S_n is possible to be extremely large as compared
with the size of the general group. So it will be nice if we can know the
results of the general case. It is a natural motive.

*******************************************************************
Swastik

I found the problem very natural and interesting. Given that we wish to
solve the membership problem, the presentation of the
group as a subgroup of a permutation group looks like the neatest way to
formulate the problem.

However, I'm not terribly fond of this algorithm, partly because it is
isolated in that no other algorithm will use this (is there some standard
problem that needs membership queries solved on groups presented as
subgroups of permutation groups with generators?), nor does it build upon
any useful computational/algebraic tools, and partly because
there isn't really a clear paradigm to be taken away (is there? maybe if
this could be explained it could illuminate the algorithm a bit more).

So I'd like to go on to the next topic, and see some actual theory
building happening.

*******************************************************************
Victor

Suppose G=<S> is a subgroup of the permutation group S_n. The lecture showed an memership
algorithm that efficiently determines if a given permutation pi is in G or not.

Checking if pi can be written as a product of G's generator is not a good approach as
some must have exponentially long sequences. To describe the algorithm, the notion of a
strong generating set was introduced. Easy arguments show that every group G must have a
SGS set T, such that T is small, and the "closure" of T is G itself. So if the algorithm
has access to a SGS set T of a group G, then it can be shown that the membership question
can be decided easily. This can be done recursively.

Then we characterized the notion of a SGS T. Once this is shown, then we can design an
algorithm that constructs T. Since T is minimal, the algorithm at each step adds an
element that makes T closer to satisfying the conditions of being a SGS. Once this was
done, the algorithm becomes complete.

The lecture is self-contained and gives me enough intuition. Though I missed some steps
in the reasoning in class, the prenotes was sufficiently clear and fills in the details
that I missed. It would be nice if prenotes is available more often, especially when the
material is not easy to find elsewhere.

*******************************************************************

Paul

At first glance thi problem discussed in lecture -- of finding a sequence
of permutations that takes an element to an arbitrary other element --
seems to have the flavor of many well-known NP-complete problems.  I
mentioned the result to a friend and he immediately asked if something
like that would solve his problem: find a sequence of deformations of a
protein that would shape it so as to bind to a certain ligand.  And the
answer is that his problem, and anything like it, is probably NP-complete;
the hard part is pinpointing what makes the permutation group special.

Most algorithms in computer science are enormously flexible.  Sorting, for
example, is probably used in any industrial application in existence, but
there is never any need for new sorting algorithms.  Linear programming is
now being widely used to approximate NP complete problems.  In general,
many algorithms can be used in contexts well outside those they were
designed for.

The algorithm we saw in class, however, doesn't seem to have this kind of
flexibility, adaptability.  Another problem that appears similar to the
permutation group problem is the shortest vector in a lattice problem.  A
lattice is of course also a group structure, and the problem is that we
may have been given the "wrong" generators -- i.e. not the shortest ones.
This seems very similar to the issues we faced in the permutation group,
finding the strongly generating set etc.  However, apparently, our
approach does not carry over to the other domain.

I don't have much of an answer to the question of why our algorithm
appears so inflexible, I just mean to pose the question.

On a side note -- you asked if there were generators that required
exponential interleaving.  I think the generators we found during office
hours on Thursday (?) work -- the pair a,b such that a,b have order 2
while ab has exponential order.

*******************************************************************

Josh

Overall I thought the lecture was quite good.  The pictures in
particular made it quite clear what was going on, even when no one can
remember whether the order in which we mean to multiply permutations.

Initially, your defn of closure was a bit unclear (at least to me),
but after your formalized it a bit more it was fine.

The notation k(\pi) initially bothered me, since you were using
lowercase k all over the place, but I think it ended up being very
natural, since you were often writing things such as k(\pi)=k and
\pi(j)=k.

In the lecture notes, the notation Sym(k) is probably not a good idea.
Many authors who talk about permutation groups use Sym(k) to mean S_k,
as they more generally use Sym(S) for some set S to mean the group of
bijections from S to S.  You even confused the two at one point: in
Lemma 2 you say "Fix a group G \subset Sym(n)" rather than "fix G
\subset S_n".

Depending on the backgrounds of the students in the class, it might be
interesting to point out the similarities between SGS for perm gps and
Groebner bases for ideals.  (Both are defined by a sort of
"independence" property; both are defined by something that looks
unrelated to generating the initial structure, and yet both do
generate the initial structure; both allow for membership testing in a
similar manner; etc) And yet, the complexity for finding a Groebner
basis is unknown (last I checked).  Getting into Groebner bases from
scratch might take too long though :(.

If H,K are subgps of G, and S,T are SGSs for H,K resp., is there an
easy way to find an SGS for the intersection of H and K?  (I ask b/c
Groebner bases provide such an algorithm for intersection of ideals.)