Eliminating Variables: Mission Impossible?
Viktor Levandovskyy (RWTH Aachen)
Thursday 21 January 2010, 15.00, b-it 1.25 (cosec meeting room)
I am going to speak about several algorithmic procedures in
non-commutative algebra, whose development I have been following since ten years.
Computing the result of such a procedure belongs
to the hardest computational challenges I have ever seen.
All of these procedures can be realized with the help of elimination of
variables technique, but even the most powerful implementations of
Gr\"obner bases in modern computer algebra systems are only able to treat
the simplest cases. I wish to discuss approaches to at least estimate the
practical complexity of elimination of variables as one of the cornerstones
in computational algebra, both commutative and non-commutative.