Rao B .V., Raghavendra ;
Sarma M. N. , Jayalal
Isomorphism testing of readonce functions and polynomials
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
readonce formulas) is complete for logspace. 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 readonce formulas. This classifies the
complexity of the problem in terms of the number of reads, as read3
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 constantfree
readonce 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 readonce functions and polynomials}},
booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011)},
pages = {115126},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897347},
ISSN = {18688969},
year = {2011},
volume = {13},
editor = {Supratik Chakraborty and Amit Kumar},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2011/3320},
URN = {urn:nbn:de:0030drops33202},
doi = {http://dx.doi.org/10.4230/LIPIcs.FSTTCS.2011.115},
annote = {Keywords: Isomorphism Problems, Computational Complexity, Readonce formulas, Readonce Polynomials }
}
Keywords: 

Isomorphism Problems, Computational Complexity, Readonce formulas, Readonce 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 