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