Difference between revisions of "Majority"
m (→Properties) |
|||
| Line 18: | Line 18: | ||
* 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> | * 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> | ||
| + | |||
| + | == Promise Majority == | ||
| + | |||
| + | Closely associated with the majority function is the promise majority, or approximate majority problem. This is the promise version of the majority problem where the input is promised to either have at least <math>1 + \epsilon</math> fraction of input bits one, or at most <math>1 - \epsilon</math> fraction of input bits one. | ||
| + | |||
| + | We say a function <math>f:\{-1,1\}^n \to \{-1,1\}</math> solves the <math>\epsilon</math>-approximate majority problem if: | ||
| + | |||
| + | :::{| class="wikitable" | ||
| + | |- | ||
| + | |<math> \forall x \in \{x \in \{-1, 1\}^n\}: \sum_i x_i \geq 2 n \epsilon\}: f(x) = 1</math> | ||
| + | |- | ||
| + | |<math> \forall x \in \{x \in \{-1, 1\}^n\}: \sum_i x_i \leq - 2 n \epsilon\}: f(x) = -1</math> | ||
| + | |} | ||
| + | |||
| + | A randomized AC0 circuit with depth d can solve <math>\frac{1}{\ln(n)^{d-1}}</math>-approximate majority, but no depth d+1 deterministic AC0 <ref>Emanuele Viola [http://www.ccs.neu.edu/home/viola/papers/rbd.pdf | Randomness Buys Depth for Approximate Counting]. In: 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science</ref> or depth d deterministic AC0[<math>\oplus</math>] <ref>Nutan Limaye and Srikanth Srinivasan and Utkarsh Tripathi [https://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=&ved=2ahUKEwip4s72tJjqAhUJi6wKHa8RAfUQFjAAegQIAxAB&url=https%3A%2F%2Feccc.weizmann.ac.il%2Freport%2F2019%2F133%2Fdownload%2F&usg=AOvVaw3rqd5wmW-HfmXra9S3RcSE | More on AC0<math>\oplus</math> and Variants of the Majority Function]</ref>. | ||
== References == | == References == | ||
Revision as of 17:05, 23 June 2020
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
- Among all monotone functions, majority has the largest influence: [math]\mathrm{Inf}(f) \leq \mathrm{Inf}(\mathrm{Maj})[/math] for all monotone [math]f[/math] [1].
- TODO: a description of Majority's Fourier Transform. See http://www.contrib.andrew.cmu.edu/~ryanod/?p=877 for details.
- 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]
Promise Majority
Closely associated with the majority function is the promise majority, or approximate majority problem. This is the promise version of the majority problem where the input is promised to either have at least [math]1 + \epsilon[/math] fraction of input bits one, or at most [math]1 - \epsilon[/math] fraction of input bits one.
We say a function [math]f:\{-1,1\}^n \to \{-1,1\}[/math] solves the [math]\epsilon[/math]-approximate majority problem if:
[math] \forall x \in \{x \in \{-1, 1\}^n\}: \sum_i x_i \geq 2 n \epsilon\}: f(x) = 1[/math] [math] \forall x \in \{x \in \{-1, 1\}^n\}: \sum_i x_i \leq - 2 n \epsilon\}: f(x) = -1[/math]
A randomized AC0 circuit with depth d can solve [math]\frac{1}{\ln(n)^{d-1}}[/math]-approximate majority, but no depth d+1 deterministic AC0 [4] or depth d deterministic AC0[[math]\oplus[/math]] [5].
References
- ↑ Ryan O'Donnell, Analysis of Boolean functions, Theorem 32 in section 2.3
- ↑ 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
- ↑ Emanuele Viola | Randomness Buys Depth for Approximate Counting. In: 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science
- ↑ Nutan Limaye and Srikanth Srinivasan and Utkarsh Tripathi | More on AC0[math]\oplus[/math] and Variants of the Majority Function
