English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Two Boolean functions f, g : F_2^{n} \to {-1, 1} are called linearlyisomorphic if there exists an invertible matrix M \in F_2^{n\times n} such thatf\circ M = g. Testing linear isomorphism is a generalization of, now classicalin the context of property testing, isomorphism testing between Booleanfunctions. Linear-invariance of Boolean functions has also been extensivelystudied in other areas like coding theory and cryptography, and mathematics ingeneral. In this paper, we will study the following two variants of thisproblem:  [1] [Communication complexity: ] Assume that Boolean functions f and g onF_2^{n} are given to Alice and Bob respectively, and the goal is to test linearisomorphism between f and g by exchanging a minimum amount of communication,measured in bits, between Alice and Bob. Our main result is an efficienttwo-party communication protocol for testing linear isomorphism in terms of theapproximate spectral norm of the functions. We will crucially exploit theconnection between approximate spectral norm and sign-approximatingpolynomials.  [2] [Query complexity: ] If f: F_2^{n} \to { -1, 1 } is a known function andg : F_2^{n} \to { -1, 1 } be an unknown function with a query access. We studythe query complexity of testing linear isomorphism between f and g in terms ofthe approximate spectral norm of f. As in the case of communication complexity,we will use properties of the approximate spectral norm.

Linear isomorphism testing of Boolean functions with small approximate spectral norm