*BibTeX*

@Article{AKKRV15dtdliso, author = {V. Arvind and Johannes Köbler and Sebastian Kuhnert and Gaurav Rattan and Yadu Vasudev}, title = {On the isomorphism problem for decision trees and decision lists}, journal = {Theoretical Computer Science}, year = 2015, volume = 590, month = 7, pages = {38-54}, issn = {0304-3975}, doi = {10.1016/j.tcs.2015.01.025}, }

**On the isomorphism problem for
decision trees and decision lists.**

With V. Arvind,
Johannes
Köbler, Gaurav
Rattan, Yadu
Vasudev.

*Theoretical Computer Science* 590:38–54 (2015).

Abstract.We study the complexity of isomorphism testing for Boolean functions that are represented by decision trees or decision lists. Our results include a 2^{√s poly(lg s)}time algorithm for isomorphism testing of decision trees of sizes. Additionally, we show:

- Isomorphism testing of rank-1 decision trees is complete for logspace.
- For
*r*≥2, isomorphism testing for rank-*r*decision trees is polynomial-time equivalent to Graph Isomorphism. As a consequence we obtain a 2^{√s poly(lg s)}time algorithm for isomorphism testing of decision trees of size*s*. - The isomorphism problem for decision lists admits a Schaefer-type dichotomy: depending on the class of base functions, the isomorphism problem is either in polynomial time, or equivalent to Graph Isomorphism, or coNP-hard.

*BibTeX*

@InProceedings{AKKRV13dtdliso, author = {V. Arvind and Johannes Köbler and Sebastian Kuhnert and Gaurav Rattan and Yadu Vasudev}, title = {On the isomorphism problem for decision trees and decision lists}, booktitle = {Proc. 19th FCT}, pages = {16-27}, year = 2013, editor = {Leszek Gąsieniec and Frank Wolter}, series = {LNCS}, number = 8070, publisher = {Springer}, address = {Berlin}, isbn = {978-3-642-40163-3}, doi = {10.1007/978-3-642-40164-0_5}, }

Conference version:

**On the isomorphism problem for decision trees and decision
lists**

With V. Arvind,
Johannes
Köbler, Gaurav
Rattan, Yadu
Vasudev.

*Fundamentals of Computation Theory* (Proceedings of
19th FCT). Springer,
2013. Pp. 16-27.