Florida International University
Edit Your Profile
FIU Discovery
Toggle navigation
Browse
Home
People
Organizations
Scholarly & Creative Works
Research Facilities
Support
Edit Your Profile
Tight lower bounds for testing linear isomorphism
Conference
Grigorescu, E, Wimmer, K, Xie, N. (2013). Tight lower bounds for testing linear isomorphism .
EURO-PAR 2011 PARALLEL PROCESSING, PT 1,
8096 LNCS 559-574. 10.1007/978-3-642-40328-6_39
Share this citation
Twitter
Email
Grigorescu, E, Wimmer, K, Xie, N. (2013). Tight lower bounds for testing linear isomorphism .
EURO-PAR 2011 PARALLEL PROCESSING, PT 1,
8096 LNCS 559-574. 10.1007/978-3-642-40328-6_39
Copy Citation
Share
Overview
Identifiers
Additional Document Info
View All
Overview
cited authors
Grigorescu, E; Wimmer, K; Xie, N
authors
Xie, Ning
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.
publication date
October 15, 2013
published in
DISTRIBUTED COMPUTING (DISC 2014)
Book
Identifiers
Digital Object Identifier (DOI)
https://doi.org/10.1007/978-3-642-40328-6_39
Additional Document Info
start page
559
end page
574
volume
8096 LNCS