























In this short note, we initiate the study of the Linear Isomorphism Testing Problem in the setting of communication complexity, a natural linear algebraic generalization of the classical Equality problem. Given Boolean functions $f, g : \mathbb{F}_2^n \to \{-1, +1\}$, Alice and Bob are tasked with determining whether $f$ and $g$ are equivalent up to a nonsingular linear transformation of the input variables, or far from being so. This problem has been extensively investigated in several models of computation, including standard algorithmic and property testing frameworks, owing to its fundamental connections with combinatorial circuit design, complexity theory, and cryptography. However, despite its broad relevance, it has remained unexplored in the context of communication complexity, a gap we address in this work. Our main results demonstrate that the approximate spectral norm of the input functions plays a central role in governing the communication complexity of this problem. We design a simple deterministic protocol whose communication cost is polynomial in the approximate spectral norm, and complement it with nearly matching lower bounds (up to a quadratic gap). In the randomised setting with private coins, we present an even more efficient protocol, though equally simple, that achieves a quadratically improved dependence on the approximate spectral norm compared to the deterministic case, and we prove that such a dependence is essentially unavoidable. These results identify the approximate spectral norm as a key complexity measure for testing linear invariance in the communication complexity framework. As a core technical ingredient, we establish new junta theorems for Boolean functions with small approximate spectral norm, which may be of independent interest in Fourier analysis and learning theory.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。