Tight lower bounds for testing linear isomorphism Conference

Grigorescu, E, Wimmer, K, Xie, N. (2013). Tight lower bounds for testing linear isomorphism . Lecture Notes in Computer Science, 8096 LNCS 559-574. 10.1007/978-3-642-40328-6_39

cited authors

  • Grigorescu, E; Wimmer, K; Xie, N

abstract

  • We study lower bounds for testing membership in families of linear/affine-invariant Boolean functions over the hypercube. 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. 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 et al. (Computational Complexity, 2012.) Our second result shows an Ω(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. © 2013 Springer-Verlag.

authors

publication date

  • October 15, 2013

published in

Digital Object Identifier (DOI)

start page

  • 559

end page

  • 574

volume

  • 8096 LNCS