Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR13-090 | 18th June 2013 01:14

Tight Lower Bounds for Testing Linear Isomorphism


Authors: Elena Grigorescu, Karl Wimmer, Ning Xie
Publication: 18th June 2013 01:54
Downloads: 3432


We study lower bounds for testing membership in families of linear/affine-invariant Boolean functions over the hypercube. A family of functions $P\subseteq \{\{0,1\}^n \rightarrow \{0,1\}\}$ is linear/affine invariant if for any $f\in P$, it is the case that $f\circ L\in P$ for any linear/affine transformation $L$ of the domain. Motivated by the recent resurgence of attention to the permutation isomorphism problem, we first focus on families that are linearly/affinely isomorphic to some fixed function. A function $f: \{0,1\}^n \to \{0,1\}$ is called linear isomorphic to a fixed Boolean function $g$ if $f = g \circ A$
for some non-singular transformation $A$.

Our main result is a tight adaptive, two-sided $\Omega(n^2)$ lower bound for testing linear isomorphism to the inner-product function. This is the first lower bound for testing linear isomorphism to a specific function that matches the trivial upper bound. Our proof exploits the elegant connection between testing and communication complexity discovered by Blais, Brody and Matulef (Computational Complexity, 2012.) Our results are also the first instance of this connection that gives better than $\Omega(n)$ lower bound for any property of Boolean functions. These results extend to testing linear isomorphism to any fixed function in the larger class of so-called Maiorana-McFarland bent functions.

Our second result shows an $\Omega(2^{n/4})$ query lower bound for any adaptive, two-sided tester for membership in the Maiorana- McFarland class of bent functions. This class of Boolean functions is also affine-invariant and its rich structure and pseudorandom properties have been well-studied in mathematics, coding theory and cryptography.

ISSN 1433-8092 | Imprint