Difference between revisions of "Resilience"
(Created page with "== Definition == For a set of indices <math>S\subseteq [n]</math> and an assignment of variables <math>z\in\{-1,1\}^S</math>, let <math>X_S</math> be the random variable whos...") |
m |
||
| Line 8: | Line 8: | ||
|} | |} | ||
In words, restricting any set of <math>\leq r</math> bits to any value does not significantly change the expectation of the function. | In words, restricting any set of <math>\leq r</math> bits to any value does not significantly change the expectation of the function. | ||
| + | |||
| + | == Properties == | ||
| + | * If the <math> \max \{ \hat{f}(S) \mid 0<|S|\leq r\} \leq 2^{-r}\alpha</math>, then <math>f</math> is <math>(r,\alpha)</math>-resilient. <ref>Proposition 2.14 in [https://arxiv.org/abs/2012.10352 Probabilistic Aspects of Voting, Intransitivity and Manipulation] by Elchanan Mossel.</ref> | ||
== References == | == References == | ||
<references/> | <references/> | ||
Revision as of 08:48, 12 April 2021
Definition
For a set of indices [math]S\subseteq [n][/math] and an assignment of variables [math]z\in\{-1,1\}^S[/math], let [math]X_S[/math] be the random variable whose bits indexed by [math]j \in S[/math] are fixed to [math]z_j[/math], and the rest of bits are independent and uniform.
A function [math]f:\{-1,1\}^n \to \mathbb{R}[/math] is called [math](r,\alpha)[/math]-resilient if
[math]\begin{align*}\left|\mathbb{E}[f\mid S_S = z] - \mathbb{E}[f]\right| \leq \alpha && \forall |S|\leq r, z\in\{-1,1\}^S \end{align*}[/math]
In words, restricting any set of [math]\leq r[/math] bits to any value does not significantly change the expectation of the function.
Properties
- If the [math] \max \{ \hat{f}(S) \mid 0\lt |S|\leq r\} \leq 2^{-r}\alpha[/math], then [math]f[/math] is [math](r,\alpha)[/math]-resilient. [1]
References
- ↑ Proposition 2.14 in Probabilistic Aspects of Voting, Intransitivity and Manipulation by Elchanan Mossel.
