When Does Adaptivity Help Isomorphism Testing? A Fourier-Entropy Account

Suppose you are handed a black-box Boolean function on $n$ inputs and a known reference function, and you must decide, with very few evaluations, whether the black box is just the reference with its inputs relabeled. This is isomorphism testing. It is known to be cheap, independent of $n$, when the reference depends on only $k$ variables (a $k$-junta) or is invariant under permuting all but $k$ variables (a partially symmetric function). Every efficient tester known for these cases is adaptive: it chooses each query after seeing earlier answers, typically by binary-searching for relevant variables. For the closely related task of testing whether a function is some $k$-junta, adaptivity provably matters. Non-adaptive testers, which fix all queries in advance and can therefore run them in parallel, need roughly $k^{3/2}$ queries, while adaptive ones need about $k$. Nobody knows what happens for isomorphism to a specific, known target.

We propose that the answer depends on the target, not on the class. Our specific conjecture is that the cost of giving up adaptivity is governed by how spread out the target's Fourier spectrum is, measured by its Fourier entropy. The Fourier entropy is the Shannon entropy of the squared Fourier coefficients, which form a probability distribution over subsets of variables. Targets with low entropy should be testable non-adaptively at a cost independent of $k$. High-entropy targets built like the known junta lower-bound instances should inherit the polynomial penalty. Sensitivity bounds give the bridge that makes the entropy parameter usable: they bound entropy by total influence times the log of the worst-case number of sensitive coordinates. If the conjecture is right, the adaptivity question for isomorphism testing becomes a phase diagram indexed by a spectral quantity, rather than a yes/no statement about juntas.

Core Claim

Let $g$ be a known $k$-junta on $\{-1,1\}^n$. Let $H(\hat g^2)=\sum_S \hat g(S)^2\log_2(1/\hat g(S)^2)$ be its Fourier entropy, $\mathbf{I}[g]$ its total influence (the expected number of coordinates whose flip changes the output), and $s(g)$ its maximum sensitivity. We conjecture a non-adaptive two-sided $\epsilon$-tester for isomorphism to $g$ with

$$q_{\mathrm{NA}}(g,\epsilon)\;\le\;\mathrm{poly}(1/\epsilon)\cdot 2^{O(H(\hat g^2)/\epsilon)}\;\le\;2^{O(\mathbf{I}[g]\log s(g)/\epsilon)},$$

independent of both $k$ and $n$. The second inequality is exactly the entropy bound $H(\hat f^2)\le O(\mathbf{I}[f]\log s(f))$ of Degree and Sensitivity: tails of two distributions. The first inequality's form comes from the standard fact that a distribution with entropy $H$ puts all but $\epsilon$ of its mass on $2^{O(H/\epsilon)}$ outcomes.

We pair this with a lower bound. We will construct an explicit, fixed family of high-entropy targets, modeled on addressing functions, for which non-adaptive isomorphism testing needs $\tilde\Omega(k^{3/2})$ queries. Adaptive testing of the same targets costs $O(k\log k)$.

Read together, the two results say three things. There is no adaptivity gap when $H(\hat g^2)\le c\log k$ for a small enough constant $c$ relative to $\epsilon$. There is a polynomial gap near the maximal-entropy end. The relevant parameter is entropy, not $k$ and not spectral norm.

Relation to Prior Work

Two papers supply the adaptive upper bounds this proposal tries to match without adaptivity. Nearly Tight Bounds for Testing Function Isomorphism gives $\Omega(k)$ and $O(k\log k)$ adaptive bounds for isomorphism to $k$-juntas. Partially Symmetric Functions Are Efficiently Isomorphism Testable extends this to $(n-k)$-symmetric targets with $O(k\log k/\epsilon^2)$ queries, using "symmetric influence," which measures how much a function changes when a set of variables is reordered. Both analyses treat the core function as worst case on $k$ inputs, and both use adaptive samplers. We ask what survives when the queries are fixed in advance, and we let the answer depend on the target's spectrum.

Two papers motivate the gap and constrain the lower-bound side. Settling the query complexity of non-adaptive junta testing proves the $\tilde\Omega(k^{3/2}/\epsilon)$ non-adaptive bound for testing the junta class, and Adaptivity Helps for Testing Juntas gave the first separation. Their hard "yes" instances are random juntas, not one fixed known function. The bound therefore does not transfer automatically to isomorphism testing, where the tester knows $g$ exactly. Proving it for a fixed target is part of our program.

Two papers supply spectral technique. Linear isomorphism testing of Boolean functions with small approximate spectral norm shows that isomorphism under invertible linear maps admits a non-adaptive tester with $\tilde O((m/w)^4)$ queries, where $m$ is the spectral norm, by sieving out heavy Fourier coefficients. It relies on the linear-coset structure of $\mathbb{F}_2^n$, which permutations do not preserve, and its parameter $m$ blows up for many natural low-influence functions. The Fourier Entropy-Influence line motivates entropy as the right, smaller parameter. A composition theorem for the Fourier Entropy-Influence conjecture proves the FEI conjecture (entropy at most a constant times total influence) for read-once formulas with bounded-arity gates. Fourier Entropy-Influence Conjecture for Random Linear Threshold Functions proves it for random threshold functions, which have $\mathbf{I}=\Omega(\sqrt n)$. These give us whole target families with certified low entropy.

Finally, the circuit-matching papers show empirically that sensitivity statistics are strong permutation invariants. They are Enhanced Fast Boolean Matching based on Sensitivity Signatures Pruning and A Canonical-based NPN Boolean Matching Algorithm Utilizing Boolean Difference and Cofactor Signature. Both read full truth tables, so they serve as a heuristic competitor, not a sublinear method.

Research Program

The tester. The tester draws a random partition of the $n$ coordinates into $r=\mathrm{poly}(2^{H/\epsilon})$ blocks. It then queries $f$ on a pre-fixed set of points in which each block is set jointly according to random patterns. This lets it estimate the heavy Fourier coefficients of the block function $f_B$, the function on $r$ bits obtained by tying the variables in each block together. The whole query set depends only on the random seed, so the tester is non-adaptive.

Because the distribution of $f_B$ over random partitions is invariant under relabeling the variables, isomorphic $f$ and $g$ produce identically distributed block spectra. The tester accepts when the estimated heavy spectrum of $f_B$ matches, up to block relabeling, the one computed offline from $g_B$. Low entropy is what keeps the number of heavy coefficients, and hence $r$ and the estimation cost, at $2^{O(H/\epsilon)}$.

The soundness lemma. This is the main technical risk. We must show that if $f$ is $\epsilon$-far from every relabeling of $g$, the block spectra differ detectably with constant probability over the partition. The obstacle is that $f$ might agree with $g$ on its heavy spectrum while disagreeing on light mass. We plan to handle this by also estimating the total light-coefficient weight of $f_B$, which is non-adaptively estimable by noise-stability queries. We will then argue, as in the combinatorial junta analysis of the partially-symmetric paper, that $\epsilon$-farness forces a discrepancy in either the heavy part or the light weight.

The lower bound. We will fix one addressing-style target $g^\ast_k$ whose entropy is $\Theta(k)$. We will then adapt the Yao-minimax, set-size-query reduction of Settling the query complexity of non-adaptive junta testing so that the "yes" side is random relabelings of the single function $g^\ast_k$. If this fails, we fall back to the weaker $\Omega(k\log k/\epsilon^c)$-type separation style of Servedio and Tan.

Extension to partially symmetric targets. Majority on $n-k$ variables already has entropy growing with $n$, so global entropy is the wrong parameter here. The second stage would define a "core entropy": the entropy of the core function after conditioning on the Hamming weight of the symmetric block. We would combine it with symmetric influence. This stage is explicitly conditional on the junta case working.

Baselines

Adaptive tester (strongest existing method). This is the adaptive isomorphism tester of Nearly Tight Bounds for Testing Function Isomorphism and its partially symmetric generalization in Partially Symmetric Functions Are Efficiently Isomorphism Testable. It is the strongest competitor because it sets the query cost we claim non-adaptivity can match for low-entropy targets. The reported figures are asymptotic only: $O(k\log k)$ adaptive queries against an $\Omega(k)$ lower bound for $k$-juntas, and $O(k\log k/\epsilon^2)$ for $(n-k)$-symmetric targets. We found no reported empirical query counts on Lacuna for these testers. We will implement it with binary-search variable finding and implicit learning. It will run on the same oracles, targets, $\epsilon$, and seeds as ours, with each method's constants tuned on a held-out set of targets under an equal grid-search budget. Beating it means that, on low-entropy families, our non-adaptive tester reaches 2/3 success within a constant factor of the adaptive query count, while doing so in a single parallel round.

Naive reference point. This is a non-adaptive learn-then-compare procedure: draw uniform random samples, run low-degree Fourier learning at degree $O(s\log(1/\epsilon))$, which is justified by the approximation theorem of Degree and Sensitivity: tails of two distributions, and check isomorphism offline. Its sample cost grows with $n$. Beating it means our query count stays flat as $n$ grows from $2^8$ to $2^{14}$ while its count grows.

Signature competitor. This is a sampled version of the Ordered Sensitivity Vector from the Boolean-matching work. We will estimate each variable's sensitivity histogram from random points and neighbors, and compare sorted profiles. It represents the strongest practical heuristic.

Key ablation. The ablation is our tester with spectral pruning removed: all block coefficients up to a degree cutoff are estimated, rather than only the entropy-predicted heavy set. It isolates whether the entropy-driven concentration, and not the block construction itself, produces the savings.

Why not just…?

Why not just learn the function and check isomorphism offline? Learning low-sensitivity functions costs $n^{O(s\log(1/\epsilon))}$ time per Degree and Sensitivity: tails of two distributions. Identifying which variables are relevant inherently scales with $\log\binom{n}{k}$, as the hypothesis-checking comparison in Testing Junta Truncation shows. Testing needs only a relabeling-invariant fingerprint, not identification. The $n$-scaling experiment below tests this directly.

Why not just use the adaptive tester, since it already works? For query cost alone, it does. Non-adaptivity matters because it allows one fully parallel round and because it answers the open structural question of where adaptivity is necessary. We do not claim to beat the adaptive tester in query count. Our claim is that for low-entropy targets it can be matched without adaptivity, and for high-entropy ones it cannot.

Why not just reduce $g$ to a small junta and run an existing tester? This is the most serious alternative. Friedgut-style arguments say a low-influence $g$ is close to a junta on $2^{O(\mathbf{I}/\epsilon)}$ variables, which would give $k$-independence immediately. However, it converts the task into tolerant isomorphism testing, where $f$ need only be close to a relabeled junta. The only testers we have for it are adaptive, so the non-adaptive question is untouched. We will still run it with the adaptive junta-isomorphism tester applied to the Friedgut junta. If it matches our non-adaptive tester on low-entropy families, then the adaptivity result is the whole contribution and the entropy parameterization is not new. We will report that outcome.

Why not just sample sensitivity signatures, as circuit matching does? Collision counts in Enhanced Fast Boolean Matching based on Sensitivity Signatures Pruning show these signatures separate small functions well: they fell from over 124,000 collisions with symmetry signatures to under 2,000 on one million 5-variable functions. But per-variable profiles must be estimated for variables whose influence can be about $1/k$, and each estimate costs about $k$ samples. The signature baseline measures whether this is a real threat on moderate $k$.

Proposed Experiments

Oracles and target families. The benchmarks here are function classes, not datasets. We will embed each target as a $k$-junta inside $n\in\{2^8,2^{10},2^{12},2^{14}\}$ variables, using implicit oracles. The target families span the entropy axis:

  • read-once formulas with bounded fan-in (low entropy, certified by the composition theorem);
  • tribes and majority cores;
  • random threshold functions with Gaussian weights (entropy $O(\sqrt k)$ by the FEI result for random LTFs);
  • $k$-parity (entropy $k$);
  • the addressing-style family $g^\ast_k$.

We will also take single-output functions from the MCNC circuits used in A Canonical-based NPN Boolean Matching Algorithm Utilizing Boolean Difference and Cofactor Signature, and random 8–16-variable functions of the kind used in the sensitivity-signature work, as "natural" targets. We have no reported query-complexity numbers for any of these on Lacuna.

Far instances. These will be random relabelings of $g$ with planted $\epsilon$-mass perturbations. We will also use relabelings of spectrally similar but non-isomorphic functions, for example tribes with shifted clause widths.

Metric. The main metric is the minimum query budget at which each tester achieves 2/3 correct decisions on both yes and far instances, measured over $k\in\{8,\dots,256\}$ and $\epsilon\in\{0.05,0.1,0.2\}$. From this we compute the empirical adaptivity ratio $q_{\mathrm{NA}}/q_{\mathrm{A}}$.

Decisive checks. There are three:

  • The adaptivity ratio should stay bounded in $k$ for the read-once and tribes families, and grow at least as $k^{1/2}$ for $g^\ast_k$.
  • Across all targets, the log of the non-adaptive query count should be explained by $H(\hat g^2)/\epsilon$ markedly better than by $\log k$, $\mathbf{I}[g]$, or spectral norm, compared by out-of-family regression fit.
  • Our query count should not grow with $n$, while the learn-then-compare baseline's does.

What would refute the claim. Any of the following would falsify the entropy conjecture:

  • the ablation matches the full tester;
  • the Friedgut-reduction baseline matches it without adaptivity;
  • entropy predicts no better than $k$.