@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 size s. 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.

@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.