Pith. sign in

Boolean functions whose Fourier transform is concentrated on pairwise disjoint subsets of the input

1 Pith paper cite this work. Polarity classification is still indexing.

1 Pith paper citing it
abstract

We consider Boolean functions f:{-1,1}^n->{-1,1} that are close to a sum of independent functions on mutually exclusive subsets of the variables. We prove that any such function is close to just a single function on a single subset. We also consider Boolean functions f:R^n->{-1,1} that are close, with respect to any product distribution over R^n, to a sum of their variables. We prove that any such function is close to one of the variables. Both our results are independent of the number of variables, but depend on the variance of f. I.e., if f is \epsilon*Var(f)-close to a sum of independent functions or random variables, then it is O(\epsilon)-close to one of the independent functions or random variables, respectively. We prove that this dependence on Var(f) is tight. Our results are a generalization of the Friedgut-Kalai-Naor Theorem [FKN'02], which holds for functions f:{-1,1}^n->{-1,1} that are close to a linear combination of uniformly distributed Boolean variables.

fields

cs.CC 1

years

2026 1

verdicts

CONDITIONAL 1

representative citing papers

An FKN Theorem for the Binary Grassmann Scheme

cs.CC · 2026-08-11 · conditional · novelty 8.0

A Boolean function on the Grassmann scheme over F2 that is close to a degree 1 function is close to a canonical point/hyperplane indicator sum, up to complement.

citing papers explorer

Showing 1 of 1 citing paper.

  • An FKN Theorem for the Binary Grassmann Scheme cs.CC · 2026-08-11 · conditional · none · ref 11 · internal anchor

    A Boolean function on the Grassmann scheme over F2 that is close to a degree 1 function is close to a canonical point/hyperplane indicator sum, up to complement.