%0 Generic %1 Torán_onthe %A Torán, Jacobo %D 2004 %K 2013 graph hardness isomorphism %T On the Hardness of Graph Isomorphism %U http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.142.1448 %X We show that the graph isomorphism problem is hard under DLOGTIME uniform AC0 many-one reductions for the complexity classes NL, PL (probabilistic logarithmic space) for every logarithmic space modular class ModkL and for the class DET of problems NC¹ reducible to the determinant. These are the strongest known hardness results for the graph isomorphism problem and imply a randomized logarithmic space reduction from the perfect matching problem to graph isomorphism. We also investigate hardness results for the graph automorphism problem.

@misc{Torán_onthe, abstract = {We show that the graph isomorphism problem is hard under DLOGTIME uniform AC0 many-one reductions for the complexity classes NL, PL (probabilistic logarithmic space) for every logarithmic space modular class ModkL and for the class DET of problems NC¹ reducible to the determinant. These are the strongest known hardness results for the graph isomorphism problem and imply a randomized logarithmic space reduction from the perfect matching problem to graph isomorphism. We also investigate hardness results for the graph automorphism problem.}, added-at = {2014-02-18T12:00:11.000+0100}, author = {Torán, Jacobo}, biburl = {https://www.bibsonomy.org/bibtex/27fb196c54ea314261d68197a25cdf763/s_nkeha}, description = {On the Hardness of Graph Isomorphism}, interhash = {4d528b8709dafa1827ec243c2368394a}, intrahash = {7fb196c54ea314261d68197a25cdf763}, keywords = {2013 graph hardness isomorphism}, timestamp = {2014-02-18T12:00:11.000+0100}, title = {On the Hardness of Graph Isomorphism}, url = {http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.142.1448}, year = 2004 }