License: Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license (CC BY-NC-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2011.115
URN: urn:nbn:de:0030-drops-33202
URL: https://drops.dagstuhl.de/opus/volltexte/2011/3320/
Go to the corresponding LIPIcs Volume Portal

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

Isomorphism testing of read-once functions and polynomials

pdf-format:
2.pdf (0.4 MB)

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 =		{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
Collection: 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 | Privacy Published by LZI