Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > PARITIES:
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