Difference between revisions of "Majority"
m |
m |
||
| (11 intermediate revisions by 3 users not shown) | |||
| Line 16: | Line 16: | ||
* TODO: a description of Majority's Fourier Transform. See http://www.contrib.andrew.cmu.edu/~ryanod/?p=877 for details. | * 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 [[: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. | ||
| + | * The majority function is [[:Category:evasive function|evasive]] so the [[decision tree complexity]] is <math>D(f) = n</math>. | ||
* 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 | + | * Majority is [[noise stability | noise stable]] but is not [[volatility|tame]]. <ref>Johan Jonasson, Jeffrey E. Steif, [https://www.sciencedirect.com/science/article/pii/S0304414916000648 Volatility of Boolean functions], Stochastic Processes and their Applications, Proposition 1.15</ref> |
| + | * [[Circuit_complexity#AC0 | AC<sup>0</sup>]] circuits of depth <math>d \geq 2</math> even ''approximating'' majority (outputting the same value as majority for a constant fraction more than half of the inputs) requires size <math>2^{\Theta(n^{1/(2d-1)})}</math><ref>Kazuyuki Amano, [https://arxiv.org/abs/0902.0047 Bounds on the Size of Small Depth Circuits for Approximating Majority], in Proceedings of the 36th International Colloquium on Automata, Languages and Programming: Part I, pages 59-70.</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> | ||
| + | * Majority is <math>(r,r/\sqrt{n})</math>-[[resilience | resilient]]. | ||
== Promise Majority == | == Promise Majority == | ||
| Line 23: | Line 27: | ||
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. | 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>- | + | We say a function <math>f:\{-1,1\}^n \to \{-1,1\}</math> solves the <math>\epsilon</math>-promise majority problem if: |
:::{| class="wikitable" | :::{| class="wikitable" | ||
| Line 29: | Line 33: | ||
|<math> f(x) = \begin{cases} 1, & if ~ \sum_i x_i \geq 2 n \epsilon \\ | |<math> f(x) = \begin{cases} 1, & if ~ \sum_i x_i \geq 2 n \epsilon \\ | ||
-1 & if ~ \sum_i x_i \leq - 2 n \epsilon \\ | -1 & if ~ \sum_i x_i \leq - 2 n \epsilon \\ | ||
| − | 1 \text{ or } -1 & otherwise \end{cases} | + | 1 \text{ or } -1 & otherwise \\ |
| + | \end{cases} </math> | ||
|} | |} | ||
| − | A randomized [[Circuit_complexity#AC0 | AC<sup>0</sup>]] circuit with depth d can solve <math>\frac{1}{\ln(n)^{d-1}}</math>- | + | This is different from the usual meaning of approximating a boolean function where we require it computes the function on most inputs. |
| + | |||
| + | A randomized [[Circuit_complexity#AC0 | AC<sup>0</sup>]] circuit with depth <math>d \geq 2</math> can solve <math>\frac{1}{\ln(n)^{d-1}}</math>-promise majority, but no depth d+1 deterministic [[Circuit_complexity#AC0 | AC<sup>0</sup>]] <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 name="MoreOnAC0">Nutan Limaye and Srikanth Srinivasan and Utkarsh Tripathi, [https://eccc.weizmann.ac.il/report/2019/133/ More on AC0<math>\oplus</math> and Variants of the Majority Function]. In: 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019)</ref> can do so. | ||
| + | |||
| + | |||
| + | If polynomial p has | ||
| + | |||
| + | :::{| class="wikitable" | ||
| + | |- | ||
| + | |<math> \Pr_{x \sim \{x \in \{-1, 1\}^n: \sum_i x_i \geq n/\ln(n)^c\}}[p(x) = -1] \leq 1/n </math> | ||
| + | |- | ||
| + | |<math> \Pr_{x \sim \{x \in \{-1, 1\}^n: \sum_i x_i \leq -n/\ln(n)^c\}}[p(x) = 1] \leq 1/10 </math> | ||
| + | |} | ||
| + | |||
| + | Then p must have degree at least <math>\Omega(\ln(n)^{c+1})</math>. | ||
| + | |||
| + | Loosely, any polynomial p approximately solving the <math>\frac{1}{\ln(n)^c}</math>-promise majority must have degree <math>\Omega(\ln(n)^{c+1})</math> <ref name="MoreOnAC0" />. | ||
== References == | == References == | ||
<references/> | <references/> | ||
| − | [[Category:symmetric function]] [[Category:monotone function]] [[Category:balanced function]] [[Category:odd function]] | + | [[Category:symmetric function]] [[Category:monotone function]] [[Category:balanced function]] [[Category:evasive function]] [[Category:odd function]] [[Category:Noise stable function]] |
Latest revision as of 10:28, 20 March 2022
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.
- The majority function is evasive so the decision tree complexity is [math]D(f) = n[/math].
- Majority is not in AC0, even if we allow using mod q functions as gates for prime [math]q[/math]. [2]
- Majority is noise stable but is not tame. [3]
- AC0 circuits of depth [math]d \geq 2[/math] even approximating majority (outputting the same value as majority for a constant fraction more than half of the inputs) requires size [math]2^{\Theta(n^{1/(2d-1)})}[/math][4].
- 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]. [5]
- Majority is [math](r,r/\sqrt{n})[/math]- resilient.
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]-promise majority problem if:
[math] f(x) = \begin{cases} 1, & if ~ \sum_i x_i \geq 2 n \epsilon \\ -1 & if ~ \sum_i x_i \leq - 2 n \epsilon \\ 1 \text{ or } -1 & otherwise \\ \end{cases} [/math]
This is different from the usual meaning of approximating a boolean function where we require it computes the function on most inputs.
A randomized AC0 circuit with depth [math]d \geq 2[/math] can solve [math]\frac{1}{\ln(n)^{d-1}}[/math]-promise majority, but no depth d+1 deterministic AC0 [6] or depth d deterministic AC0[[math]\oplus[/math]] [7] can do so.
If polynomial p has
[math] \Pr_{x \sim \{x \in \{-1, 1\}^n: \sum_i x_i \geq n/\ln(n)^c\}}[p(x) = -1] \leq 1/n [/math] [math] \Pr_{x \sim \{x \in \{-1, 1\}^n: \sum_i x_i \leq -n/\ln(n)^c\}}[p(x) = 1] \leq 1/10 [/math]
Then p must have degree at least [math]\Omega(\ln(n)^{c+1})[/math].
Loosely, any polynomial p approximately solving the [math]\frac{1}{\ln(n)^c}[/math]-promise majority must have degree [math]\Omega(\ln(n)^{c+1})[/math] [7].
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.
- ↑ Johan Jonasson, Jeffrey E. Steif, Volatility of Boolean functions, Stochastic Processes and their Applications, Proposition 1.15
- ↑ Kazuyuki Amano, Bounds on the Size of Small Depth Circuits for Approximating Majority, in Proceedings of the 36th International Colloquium on Automata, Languages and Programming: Part I, pages 59-70.
- ↑ 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
- ↑ 7.0 7.1 Nutan Limaye and Srikanth Srinivasan and Utkarsh Tripathi, More on AC0[math]\oplus[/math] and Variants of the Majority Function. In: 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019)
