Tagged Questions
1
vote
3answers
129 views
Boolean algebra probability not coming out right
Assuming A,B,C,D are mutually independent.
$P[(A\cup\overline{B}\cup C)\cap(A\cup C \cup \overline{D})]$
I get $(P(A) + 1 - P(B) + P(C))(P(A) + P(C) + 1 - P(D))$
But when I plug in the numbers, I ...
1
vote
1answer
64 views
The fraction of k-juntas with low influences in all of the coordinates
Let $f:\{-1,1\}^n\to\{-1,1\}$ be a boolean function.
Define the influence of the $i$'th coordinate of $f$ as follows:
$$\operatorname{Inf}_i(f)=\Pr_{x}[f(x)\neq f(\hat x_i)]$$
where $x$ is uniformly ...
4
votes
1answer
157 views
A Boolean function with total influence 1 must be a dictatorship
Let $f:\{-1,1\}^n\to\{-1,1\}$ be a boolean function.
Define the influence of the $i$'th coordinate of $f$ as follows:
$$\operatorname{Inf}_i(f)=\Pr_{x}[f(x)\neq f(\hat x_i)]$$
where $x$ is uniformly ...
3
votes
2answers
57 views
Parity is the only function with maximal influences
Let $f:\{-1,1\}^n\to\{-1,1\}$ be a boolean function.
Define the influence of the $i$'th coordinate of $f$ as follows:
$$\operatorname{Inf}_i(f)=\Pr_{x}[f(x)\neq f(\hat x_i)]$$
where $x$ is uniformly ...
