Difference between revisions of "Majority"
m |
m (→Properties) |
||
| Line 16: | Line 16: | ||
* Majority is the unique function that is [[:Category:symmetric function|symmetric]], [[:Category:monotone function|monotone]] and [[:Category:odd function|odd]] function. TODO May's theorem, credit. | * Majority is the unique function that is [[:Category:symmetric function|symmetric]], [[:Category:monotone function|monotone]] and [[:Category:odd function|odd]] function. TODO May's theorem, credit. | ||
* Majority is not in [[Circuit_complexity#AC0 | AC<sup>0</sup>]], even if we allow using [[mod q]] functions as gates for prime <math>q</math>. <ref>A. Razborov, Lower bounds on the size of bounded-depth networks over a complete basis with logical addition (Russian), in Matematicheskie Zametki, Vol. 41, No 4, 1987, pages 598-607. English translation in Mathematical Notes of the Academy of Sci. of the USSR, 41(4):333-338, 1987.</ref> | * Majority is not in [[Circuit_complexity#AC0 | AC<sup>0</sup>]], even if we allow using [[mod q]] functions as gates for prime <math>q</math>. <ref>A. Razborov, Lower bounds on the size of bounded-depth networks over a complete basis with logical addition (Russian), in Matematicheskie Zametki, Vol. 41, No 4, 1987, pages 598-607. English translation in Mathematical Notes of the Academy of Sci. of the USSR, 41(4):333-338, 1987.</ref> | ||
| + | * For every <math>\varepsilon > 0 </math>, Majority can be <math>\varepsilon</math>-approximated by a DNF of size <math>2^{O(\sqrt{n})}</math>. <ref>O’Donnell R., Wimmer K. (2007) [https://link.springer.com/chapter/10.1007/978-3-540-73420-8_19 | Approximation by DNF: Examples and Counterexamples]. In: Arge L., Cachin C., Jurdziński T., Tarlecki A. (eds) Automata, Languages and Programming. ICALP 2007. Lecture Notes in Computer Science, vol 4596. Springer, Berlin, Heidelberg</ref> | ||
== References == | == References == | ||
Revision as of 12:14, 18 November 2019
Definition
A function [math]f:\{-1,1\}^n \to \{-1,1\}[/math] is called a majority function if [math]f(x)[/math] returns the most common bit in the input:
[math] f(x) = \begin{cases} 1, & if ~ \sum_i x_i \geq 0 \\ -1 & otherwise \end{cases}[/math]
For even [math]n[/math], the above definition breaks ties in favor of 1, although any arbitrary rule may be used instead.
Majority is a special case of the perceptron function.
Properties
- Majority only depends on the number of ones and is therefore a symmetric Boolean function.
- Majority is a monotone function.
- TODO: a description of Majority's Fourier Transform. See http://www.contrib.andrew.cmu.edu/~ryanod/?p=877 for details.
- Majority is the stablest Boolean function. [1]
- Majority is the unique function that is symmetric, monotone and odd function. TODO May's theorem, credit.
- Majority is not in AC0, even if we allow using mod q functions as gates for prime [math]q[/math]. [2]
- For every [math]\varepsilon \gt 0 [/math], Majority can be [math]\varepsilon[/math]-approximated by a DNF of size [math]2^{O(\sqrt{n})}[/math]. [3]
References
- ↑ Ryan O'Donnell, Analysis of Boolean functions, [1]
- ↑ A. Razborov, Lower bounds on the size of bounded-depth networks over a complete basis with logical addition (Russian), in Matematicheskie Zametki, Vol. 41, No 4, 1987, pages 598-607. English translation in Mathematical Notes of the Academy of Sci. of the USSR, 41(4):333-338, 1987.
- ↑ O’Donnell R., Wimmer K. (2007) | Approximation by DNF: Examples and Counterexamples. In: Arge L., Cachin C., Jurdziński T., Tarlecki A. (eds) Automata, Languages and Programming. ICALP 2007. Lecture Notes in Computer Science, vol 4596. Springer, Berlin, Heidelberg
