Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH scholarly article en Rao B .V., Raghavendra; Sarma M. N. , Jayalal http://www.dagstuhl.de/lipics License
when quoting this document, please refer to the following
DOI:
URN: urn:nbn:de:0030-drops-33202
URL:

;

Isomorphism testing of read-once functions and polynomials

pdf-format:


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: 2011


DROPS-Home | Fulltext Search | Imprint Published by LZI