A structure theorem for almost low-degree functions on the slice
- PDF / 523,436 Bytes
- 43 Pages / 429.408 x 636.768 pts Page_size
- 34 Downloads / 184 Views
A STRUCTURE THEOREM FOR ALMOST LOW-DEGREE FUNCTIONS ON THE SLICE
BY
Nathan Keller∗ and Ohad Klein Department of Mathematics, Bar Ilan University, Ramat Gan 52900, Israel e-mail: [email protected], [email protected]
ABSTRACT
The Fourier–Walsh expansion of a Boolean function f : {0, 1}n → {0, 1} is its unique representation as a multilinear polynomial. The Kindler–Safra theorem (2002) asserts that if in the expansion of f , the total weight on coefficients beyond degree k is very small, then f can be approximated by a Boolean-valued function depending on at most O(2k ) variables. In this paper we prove a similar theorem for Boolean functions whose domain is the ‘slice’ [n] = {x ∈ {0, 1}n : i xi = pn}, where 0 p 1, pn with respect to their unique representation as harmonic multilinear poly nomials. We show that if in the representation of f : [n] → {0, 1}, the pn
total weight beyond degree k is at most , where = min(p, 1 − p)O(k) , then f can be O()-approximated by a degree-k Boolean function on the slice, which in turn depends on O(2k ) coordinates. This proves a conjecture of Filmus, Kindler, Mossel, and Wimmer (2015). Our proof relies on hypercontractivity, along with a novel kind of a shifting procedure. In addition, we show that the approximation rate in the Kindler–Safra theorem can be improved from + exp(O(k))5/4 to + 2 (2 ln(1/))k /k!, which is tight in terms of the dependence on and misses at most a factor of 2O(k) in the lower-order term.
∗ Research supported by the Israel Science Foundation (grants no. 402/13 and
1612/17) and the Binational US-Israel Science Foundation (grant no. 2014290). Received February 14, 2019 and in revised form August 30, 2019
1
2
N. KELLER AND O. KLEIN
Isr. J. Math.
1. Introduction 1.1. Background. For a Boolean function f : {0, 1}n → {0, 1}, the Fourier– Walsh expansion of f is its unique representation as an n-variate multilinear polynomial: f (x) = fˆ(S)χS (x), S⊂{1,2,...,n}
where χS (x) =
(−1)xi .
i∈S
The degree (or level) of a coefficient fˆ(S) is |S|, and a degree-k function is a function for which fˆ(S) vanishes for all |S| > k. The Fourier weight of f beyond degree k is W >k (f ) = fˆ(S)2 . |S|>k
(Note that by Parseval’s identity, S fˆ(S)2 is the expectation of f 2 with respect to the uniform measure on {0, 1}n.) The Friedgut–Kalai–Naor (FKN) and the Kindler–Safra (KS) theorems. The relations between the structure of a Boolean function and properties of its Fourier–Walsh expansion have been studied extensively in the last three decades. Many of the results achieved in this line of research rely on structural theorems characterizing Boolean functions whose Fourier–Walsh expansion has a ‘simple’ form. The most basic of these is the Friedgut–Kalai–Naor (FKN) theorem [26], which asserts that if most of the Fourier weight of f lies on the two bottom levels, then f essentially depends on a single coordinate. We say that Boolean functions f, g are -close if Pr[f (x) = g(x)] ≤ , where the probability is taken with respect to
Data Loading...
