Factoring Groups Efficiently

Neeraj Kayal and Timur Nezhmetdinov

2009

We give a polynomial time algorithm that computes a decomposition of a finite group G given in the form of its multiplication table. That is, given G, the algorithm outputs two subgroups A and B of G such that G is the direct product of A and B, if such a decomposition exists.

Publication type | Inproceedings |

Published in | International Colloquium on Automata, Languages and Programming (ICALP) |

URL | http://eccc.hpi-web.de/eccc-reports/2008/TR08-074/index.html |

Volume | 5555 |

Series | Lecture Notes in Computer Science |

ISBN | 978-3-642-02926-4 |

Publisher | Springer Verlag All copyrights reserved by Springer 2007. |

- A selection of lower bounds for arithmetic circuits
- A super-polynomial lower bound for regular arithmetic formulas.
- Efficient algorithms for some special cases of the polynomial equivalence problem

> Publications > Factoring Groups Efficiently