12,893 reputation
22880
bio website sci.ccny.cuny.edu/~benjamin
location New York City
age 41
visits member for 2 years, 10 months
seen 6 mins ago

I am an algebraist interested in a broad range of areas. I've worked on semigroups, geometric group theory, algebraic combinatorics, representation theory, self-similar groups (aka automaton groups), profinite groups and random walks on semigroups and groups. I've been particularly interested in interactions between these areas and Computer Science and am fond of algorithmic questions. I've also dabbled with operator algebras associated to etale groupoids and inverse semigroups. Currently, I am interested in applications of finite semigroup theory to finite state Markov chains.

My blog is http://bensteinberg.wordpress.com/author/bsteinbg/


1d
comment Computational complexity of deciding isomorphism of rational polyhedral cones
This is the tricky part to do in a way with reasonable complexity.
Apr
15
comment Schreier's index formula
Free pro-solvable groups and free pro-p groups satisfy Schreier's formula.
Apr
15
comment Schreier's index formula
@HJRW, this is why I hedged to the rf case.
Apr
14
comment Schreier's index formula
The intersection of all the terms of the derived series is trivial because the free group is residually a finite p-group and hence residually solvable. So you do get a free group and there is no contradiction.
Apr
14
comment Computational complexity of deciding isomorphism of rational polyhedral cones
I am not so convinced here. The Hermite form seems to have to do with generating the same lattice. I am asking for isomorphic cones. I don't see that this is the same as checking the Hermite form for a matrix. Can you give details?
Apr
14
comment Computational complexity of deciding isomorphism of rational polyhedral cones
The cone might not be pointed, so there may not be a hilbert basis.
Apr
14
answered Schreier's index formula
Apr
14
comment Schreier's index formula
Let me hedge and assume the group is residually finite.
Apr
14
comment Schreier's index formula
I believe only a free group satisfies Schreier's index formula and that this was first observed by van den Dries and Lubotzsky, who proved a pro-p analogue.
Apr
14
comment Computational complexity of deciding isomorphism of rational polyhedral cones
I will take a look. You are saying to cones are equivalent iff the corresponding matrices have the same Hermite normal form?
Apr
9
comment Generalized permutahedron and random polytopes
I think people generally use permutohedron to refer to the convex hull of all permutations of the entries of any vector with distinct entries. If the entries are distinct you always get the same face lattice, which is just the dual to the face lattice of the braid hyperplane arrangement. Maybe look at www-math.mit.edu/~apost/papers/permutohedron.pdf
Apr
8
comment automorphism of finitly generated group
Inna Bumagin and Daniel Wise proved it. sciencedirect.com/science/article/pii/S0022404904003111
Apr
8
comment automorphism of finitly generated group
It need not be finitely generated. Any countable group is the outer automorphism group of a fg group.
Apr
3
asked Computational complexity of deciding isomorphism of rational polyhedral cones
Apr
2
comment Complexity of counting words of given length in regular or context-free language
cseweb.ucsd.edu/~maackerman/… seems to give a polytime algorithm to enumerate lexicographically all words of length n accepted by an nfa.
Apr
2
comment Complexity of counting words of given length in regular or context-free language
A language is inherently ambiguous iff all its grammars are ambiguous. There are cfl's like that. But regular languages are never inherently ambiguous so you mean to say the grammar is ambiguous. This gets tricky.
Apr
2
comment Complexity of counting words of given length in regular or context-free language
If the grammar is context free and unambiguous the Chomsky-Schutzenberger method give a system of algebraic equations. The ambiguous case is more complicated. If the language is left regular an unambiguous you get a linear system.
Apr
2
comment Complexity of counting words of given length in regular or context-free language
This depends to some extent on how the language is given since as you said for a DFA this amounts to counting paths.
Mar
29
comment Rep of Non-Commutative Monoids
Look at the books of Putcha and Renner on algebraic monoids. The group of units of an irreducible linear algebraic monoid with 0 is reductive iff the monoid is von Neumann regular. The functions are a direct sum if irreducible one-dim reps iff the monoid is an affine toric variety in which case it is commutative.
Mar
29
comment Rep of Non-Commutative Monoids
My paper is about finite things. Your situation is quite different because you are infinite dimensional. In all situations that I am used to having a unique idempotent is the same as being a group because in a usual linear algebraic monoid the group if units is open and it's complement is an algebraic semigroup and hence has idempotents if nonempty.