Pith. sign in

REVIEW 1 cited by

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

Not yet reviewed by Pith; the record is open.

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv 1512.09045 v1 pith:JHSDWSHD submitted 2015-12-30 math.PR math.CO

classification math.PRmath.CO
keywords closefunctionsvariablesbooleanindependentfunctionproveconsider
verification ladder T0 review T1 audit T2 compute T3 formal

Signed reviews

No signed human review yet.

0 comments
read the original 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.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. An FKN Theorem for the Binary Grassmann Scheme

    cs.CC 2026-08 conditional novelty 8.0 of 10

    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.

Pith tools