Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with parities:
TR10-093 | 3rd June 2010
Sourav Chakraborty, David GarcĂ­a Soriano, Arie Matsliah

Nearly Tight Bounds for Testing Function Isomorphism

In this paper we study the problem of testing structural equivalence (isomorphism) between a pair of Boolean
functions $f,g:\zo^n \to \zo$. Our main focus is on the most studied case, where one of the functions is given (explicitly), and the other function can be queried.

We prove that for every ... more >>>

ISSN 1433-8092 | Imprint