MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Gaussian elimination makes determinant of a matrix polynomial-time computable. The reduction of complexity in computing the determinant, which is otherwise sum of exponential terms, is due to presence of alternate negative signs (lack of which makes computing permanent is #P-hard $ ie. harder then NP-C problems). This leads to some sort of symmetry in determinant, eg exchange of a pair of rows or columns just reverses the signs. I read somewhere, probably in connections with holographic algorithms introduced by Valiant, that Gaussian elimination could be explained in terms of group action and this in turns leads to generic techniques in complexity reduction.

Also, i feel that almost all source of complexity reduction for any computational problem is some sort of symmetry present. Is it true? Can we rigorously formalize this in terms of group theory?

share|cite|improve this question
Crossposted from… . – Emil Jeřábek Aug 28 '12 at 13:22
@Emil I did not get answer there.. so I posted here as well. Should I remove one of the questions? Which one? – DurgaDatta Aug 28 '12 at 14:14
Simultaneous cross-posting is generally not welcome, as it fragments the discussion and makes people duplicate the effort. It makes sense to reask the question on another forum if you do not get an answer, but you should wait at least a couple of days, not 3 hours, especially on a relatively low-traffic site like cstheory.SE. In any case, you should link the two questions to each other so that people are aware of it (as I did above). I don’t think it’s necessary to remove the question, but please keep this in mind for the future. – Emil Jeřábek Aug 28 '12 at 14:30
You mean the left action by multiplication of the group of lower-triangular unipotent matrices? – Will Sawin Aug 28 '12 at 14:55
Thank you @Emil. I will keep that in mind. – DurgaDatta Aug 28 '12 at 15:12

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.