4,484 reputation
725
bio website cs.ox.ac.uk/people/…
location Oxford, United Kingdom
age 51
visits member for 4 years, 2 months
seen 1 hour ago

Feb
16
revised Algorithm to solve Sokoban-like game on graphs - move chips from one set of vertices to another
added 58 characters in body
Feb
16
revised Algorithm to solve Sokoban-like game on graphs - move chips from one set of vertices to another
fixed the 2nd reference
Feb
16
comment Algorithm to solve Sokoban-like game on graphs - move chips from one set of vertices to another
I'll blame my wife - I never played Sokoban myself ;)
Feb
16
comment Algorithm to solve Sokoban-like game on graphs - move chips from one set of vertices to another
how are you going to do 1) in polytime?
Feb
15
answered Algorithm to solve Sokoban-like game on graphs - move chips from one set of vertices to another
Feb
15
answered Algorithm to solve Sokoban-like game on graphs - move chips from one set of vertices to another
Feb
15
comment Algorithm to solve Sokoban-like game on graphs - move chips from one set of vertices to another
yes, chip="фишка"
Feb
15
comment Algorithm to solve Sokoban-like game on graphs - move chips from one set of vertices to another
It seems to be a computationally hard problem, in the sense that every algorithm will need time exponential in $m$.
Feb
15
comment Algorithm to solve Sokoban-like game on graphs - move chips from one set of vertices to another
IMHO it's better to formulate this in terms of $m$ chips placed on nodes of your digraph $G$, at most one chip on a node, and each move in this game, with the goal is to place chips on a fixed subset of "final" nodes, is to move a chip on a node $v$ to the other end $u$ of an arc $vu$, without violating the condition that there is at most one chip on a node.
Feb
15
comment Algorithm to solve Sokoban-like game on graphs - move chips from one set of vertices to another
it's not clear what are moves allowed. Are you moving the 'init_j' vertices at the same time? By the way, "wave algorithm" seems to be what is called "breadth-first search" in English.
Feb
10
answered complexity of finding optimal matchings of given fixed size
Feb
10
comment Find a convex hull that contains given points?
the idea is to choose pairs $\pm v_i$ of maximal norm, IMHO...
Feb
10
comment basics of classification of trilinear forms (when is it non-discrete)
MathSciNet shows 2 references on the paper you cited, have a look!
Feb
10
comment basics of classification of trilinear forms (when is it non-discrete)
In the case $n_1=n_2=n_3$, isn't it the same as classification of non-associative algebras? That was worked on a lot by A.Albert, etc.
Feb
10
comment Mclaughlin Graph
You most probably don't have AtlasRep installed. Try gap> LoadPackage("AtlasRep"); (i.e. one ';', not two - which suppresses output). I guess it will return 'fail'.
Feb
4
comment Factorization of bivariate polynomial
well, there are branches of mathematics, commutative algebra, and algebraic geometry, which, among other, deal with questions like this. In general, bivariate polynomials (with coefficients in an infinite field) almost never factor.
Jan
19
comment Generating function of a regular language
Aren't you are looking for what is known "transfer matrix method" in enumerative combinatorics? see e.g. Sect.4.7 in vol. 1 of R.Stanley book Enumerative Combinatorics
Jan
12
revised Over which fields are symmetric matrices diagonalizable ?
proper matrix typesetting
Jan
11
comment A sum related to the Johnson association scheme
Well, it might be it - no simpler formula. Often this is the case, e.g. check out recent work of A.Schrijver and his collaborators on improved bounds for codes, such as arxiv.org/abs/1005.4959, homepages.cwi.nl/~lex/files/codes.pdf. However, often sums like yours come up as entries of a certain matrix, and this matrix might have a reasonably nice $LU$ decomposition. E.g. in your case $L$ might be having entries ${n \choose k}$.
Jan
10
comment Largest permutation group without 2-cycles or 3-cycles
oops, you're right. I somehow didn't think straight enough when I realized that the example in the question can be improved. :-)