Difference between revisions of "Category:Balanced function"
(Renan moved page Category:Balanced function to Category:Baised function) (Tag: New redirect) |
m (Biased and balanced are different) (Tag: Removed redirect) |
||
| Line 1: | Line 1: | ||
| − | + | == Definition == | |
| + | A Boolean function <math>f:\{-1,1\}^n \to \{-1,1\}</math> is '''balanced''' if it obtains the value 1 on exactly half of its inputs. This can be written as: | ||
| + | |||
| + | <math>\sum_{x\in\{-1,1\}^n} f(x) = 0</math>. | ||
| + | |||
| + | This also has a probabilistic view: if <math>X</math> is a uniformly random vector in <math>\{-1,1\}^n</math>, then <math>\mathbb{E}f(X) = 0</math>. | ||
| + | |||
| + | A function which is not balanced is [[:Category:Biased function|biased]]. | ||
| + | |||
| + | == Properties == | ||
| + | * TODO | ||
| + | |||
| + | == Examples of balanced functions == | ||
| + | * [[Address]] | ||
| + | * [[Dictator]] | ||
| + | * [[Inner product]] | ||
| + | * [[Majority]] | ||
| + | * [[Parity]] | ||
| + | |||
| + | == References == | ||
| + | <references/> | ||
Revision as of 10:50, 5 September 2018
Definition
A Boolean function [math]f:\{-1,1\}^n \to \{-1,1\}[/math] is balanced if it obtains the value 1 on exactly half of its inputs. This can be written as:
[math]\sum_{x\in\{-1,1\}^n} f(x) = 0[/math].
This also has a probabilistic view: if [math]X[/math] is a uniformly random vector in [math]\{-1,1\}^n[/math], then [math]\mathbb{E}f(X) = 0[/math].
A function which is not balanced is biased.
Properties
- TODO
Examples of balanced functions
References
Pages in category "Balanced function"
The following 17 pages are in this category, out of 17 total.
