2
$\begingroup$

I am searching for generalizations of analysis of Boolean functions when the input strings are distributed according to a general non-uniform distribution, possibly with arbitrary dependencies between the different input bits. I know of $p$-biased analysis, but I'm facing the setting where there can be correlations between the different input bits $x_i$.

Specifically, I have the following question.

Background: The average sensitivity of a Boolean function $f : \{-1,1\}^n \rightarrow \{-1,1\}$ is $as(f) := \mathbb{E}_x[s(f,x)]$, where $s(f,x)$ is the number of Hamming neighbors $x'$ of $x$ such that $f(x) \neq f(x')$. Here, the expectation $\mathbb{E}_x$ is over the uniform distribution over $\{-1,1\}^n$. In this setting, low average sensitivity guarantees approximation by low-degree polynomials: If $\hat{f}(S)$ is the Fourier coefficient associated to the set $S \subset \{X_1, \dots, X_n\}$, then $as(f) = \sum_{S} |\hat{f}(S)|^2 |S|$ (e.g. shown in Section 3.3 of Ryan O'Donnell's tutorial https://www.cs.cmu.edu/~odonnell/papers/analysis-survey.pdf). Therefore, by Markov's inequality and the Parseval theorem, a polynomial of degree $as(f)/\epsilon^2$ is sufficient to approximate $f$ up to $\ell_2$ error $\epsilon$.

My question is: Is there any known way to generalize this to the setting where the distribution of $x \in \{-1,1\}^n$ is not uniform? That is, is there an average-sensitivity-like measure that bounds the degree of a polynomial approximating the function in $\ell_2$, where all expectations over input strings $x$ are taken w.r.t. the given non-uniform distribution? (Complexity measures other than polynomial degree are also welcome.)

I can think of a couple of generalizations of average sensitivity that appear reasonable to me. To give a specific example, take the following averaged version of block sensitivity: $$\max_{d} \sum_{i=1}^{|d|} Var[f|X_i : X_i \not\in d_i]$$ where $d$ runs over all partitions of $\{X_1, ..., X_n\}$ into disjoint subsets. This measure evaluates, for each subset $d_i$, how sensitive $f$ is to that specific subset, on average across the input strings $x$ distributed according to the given nonuniform distribution. For the uniform distribution, it is equal to the ordinary average sensitivity $as(f)$. Can this, or a similar, sensitivity measure tell us something about the polynomial degree (or decision tree depth, ...) needed to approximate $f$ in $\ell_2$ (or some other metric)?

Any pointers, ideas, or thoughts would be extremely appreciated! Thanks for your help!

Addition: Why is the `standard' definition $as(f) := \mathbb{E}_x[s(f,x)]$ not a sufficient answer? (Responding to question asked by Stella Biderman): First, I don't know how to prove in the non-uniform setting that low average sensitivity entails approximability with low-degree polynomials, as is known in the uniform setting. Second, it seems to provide answers that do not match the polynomial degree necessary for approximation: Consider the distribution $P_0$ putting almost all ($1-\epsilon$) of its mass on $1^n$, and let $f$ be the PARITY function. Then $\mathbb{E}_{x\sim{P_0}}[s(f,x)] = n$, even though $f$ is almost a constant function. If low average sensitivity corresponds to low-degree approximability (as is the case for the unifrm distribution), then this is undesirable, as a constant is sufficient to approximate $f$ up to $\ell_2$ error $\epsilon$, under the given distribution. In contrast, the proposed sensitivity metric $\max_{d} \sum_{i=1}^{|d|} Var[f|X_i : X_i \not\in d_i]$ gives a value of about $\epsilon$.

$\endgroup$
  • $\begingroup$ It seems to me that the obvious generalization of sensitivity is to take the expected value over $x\sim\mathcal{D}$ for some distribution $\mathcal{D}$. Your question implies that there are other notions of average sensitivity that appeal to you. What are they? In any event, for this generalization (as long as the domain is discrete) you can compute the answer by using the linearity of the expectation. $\endgroup$ – Stella Biderman Aug 8 at 19:58
  • 1
    $\begingroup$ Thanks for your reply! I added a section explaining why the standard definition, taking the expected value over $x \sim \mathcal{D}$, does not seem to be sufficient. $\endgroup$ – Michael Hahn Sep 14 at 15:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.