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/

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

### 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},
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