License
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2011.115
URN: urn:nbn:de:0030-drops-33202
URL: http://drops.dagstuhl.de/opus/volltexte/2011/3320/
Go to the corresponding Portal


Rao B .V., Raghavendra ; Sarma M. N. , Jayalal

Isomorphism testing of read-once functions and polynomials

pdf-format:
Document 1.pdf (396 KB)


Abstract

In this paper, we study the isomorphism testing problem of formulas in the Boolean and arithmetic settings. We show that isomorphism testing of Boolean formulas in which a variable is read at most once (known as read-once formulas) is complete for log-space. In contrast, we observe that the problem becomes polynomial time equivalent to the graph isomorphism problem, when the input formulas can be represented as OR of two or more monotone read-once formulas. This classifies the complexity of the problem in terms of the number of reads, as read-3 formula isomorphism problem is hard for \co\NP. We address the polynomial isomorphism problem, a special case of polynomial equivalence problem which in turn is important from a cryptographic perspective[Patarin EUROCRYPT'96, and Kayal SODA'11]. As our main result, we propose a deterministic polynomial time canonization scheme for polynomials computed by constant-free read-once arithmetic formulas. In contrast, we show that when the arithmetic formula is allowed to read a variable twice, this problem is as hard as the graph isomorphism problem.

BibTeX - Entry

@InProceedings{raobv_et_al:LIPIcs:2011:3320,
  author =	{Raghavendra Rao B .V. and Jayalal Sarma M. N. },
  title =	{{Isomorphism testing of read-once functions and polynomials}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011)},
  pages =	{115--126},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-34-7},
  ISSN =	{1868-8969},
  year =	{2011},
  volume =	{13},
  editor =	{Supratik Chakraborty and Amit Kumar},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2011/3320},
  URN =		{urn:nbn:de:0030-drops-33202},
  doi =		{http://dx.doi.org/10.4230/LIPIcs.FSTTCS.2011.115},
  annote =	{Keywords: Isomorphism Problems, Computational Complexity, Read-once formulas, Read-once Polynomials }
}

Keywords: Isomorphism Problems, Computational Complexity, Read-once formulas, Read-once Polynomials
Seminar: IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011)
Issue Date: 2011
Date of publication: 01.12.2011


DROPS-Home | Fulltext Search | Imprint Published by LZI