We study lower bounds for testing membership in families of linear/affine-invariant Boolean functions over the hypercube. A family of functions P01n01 is linear/affine invariant if for any fP, it is the case that fLP 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:01n01 is called linear isomorphic to a fixed Boolean function g if f=gAfor some non-singular transformation A.

Our main result is a tight adaptive, two-sided (n2) 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 (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 (2n4) 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.