Tagged Questions
3
votes
3answers
131 views
The sum of a polynomial over a boolean affine subcube
Let $P:\mathbb{Z}_2^n\to\mathbb{Z}_2$ be a polynomial of degree $k$ over the boolean cube.
An affine subcube inside $\mathbb{Z}_2^n$ is defined by a basis of $k+1$ linearly independent vectors and an ...
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 ...
