Difference between revisions of "Category:Symmetric function"
(Created page for symmetric functions. Mostly copy-pasted from Wikipedia) |
(→Properties) |
||
| (8 intermediate revisions by 3 users not shown) | |||
| Line 1: | Line 1: | ||
| + | ==Definition == | ||
A '''symmetric Boolean function''' is a Boolean function whose value does not depend on the permutation of its input bits, i.e., it depends only on the number of ones in the input. | A '''symmetric Boolean function''' is a Boolean function whose value does not depend on the permutation of its input bits, i.e., it depends only on the number of ones in the input. | ||
| Line 5: | Line 6: | ||
==Properties== | ==Properties== | ||
* A restricted Boltzman machine with <math>n</math> input units and <math>n^2+1</math> hidden units can represent any symmetric Boolean function. <ref>Theorem 7 in James Martens, Arkadev Chattopadhyay, Toniann Pitassi, Richard Zemel, [https://www.cs.toronto.edu/~toni/Papers/nips2013.pdf On the Representational Efficiency of Restricted Boltzmann Machines], NIPS 2013</ref> | * A restricted Boltzman machine with <math>n</math> input units and <math>n^2+1</math> hidden units can represent any symmetric Boolean function. <ref>Theorem 7 in James Martens, Arkadev Chattopadhyay, Toniann Pitassi, Richard Zemel, [https://www.cs.toronto.edu/~toni/Papers/nips2013.pdf On the Representational Efficiency of Restricted Boltzmann Machines], NIPS 2013</ref> | ||
| + | * A symmetric function has [[nearest neighbor representation|nearest neighbor]] complexity bounded by <math>NN(f) \leq n+1</math>. <ref>Péter Hajnal, Zhihao Liu, György Turán, [https://arxiv.org/pdf/2004.01741.pdf Nearest neighbor representations of Boolean functions], Proposition 3</ref> | ||
==Examples== | ==Examples== | ||
| + | TODO: this was taken from Wikipedia. Please create the function pages for these functions, add the symmetric category tag to them, and then delete them from the examples list. | ||
*'''Threshold functions''': their value is 1 on input vectors with ''k'' or more ones for a fixed ''k'' | *'''Threshold functions''': their value is 1 on input vectors with ''k'' or more ones for a fixed ''k'' | ||
*'''Exact-value functions''': their value is 1 on input vectors with ''k'' ones for a fixed ''k'' | *'''Exact-value functions''': their value is 1 on input vectors with ''k'' ones for a fixed ''k'' | ||
* '''Counting functions''' : their value is 1 on input vectors with the number of ones congruent to ''k'' mod ''m'' for fixed ''k'', ''m'' | * '''Counting functions''' : their value is 1 on input vectors with the number of ones congruent to ''k'' mod ''m'' for fixed ''k'', ''m'' | ||
| − | |||
== References == | == References == | ||
<references/> | <references/> | ||
| + | |||
| + | [[Category:transitive-symmetric function]] | ||
Latest revision as of 09:19, 28 October 2020
Contents
Definition
A symmetric Boolean function is a Boolean function whose value does not depend on the permutation of its input bits, i.e., it depends only on the number of ones in the input.
From the definition it follows that there are 2n+1 symmetric n-ary Boolean functions. It implies that instead of the truth table, traditionally used to represent Boolean functions, one may use a more compact representation for an n-variable symmetric Boolean function: the (n + 1)-vector, whose i-th entry (i = 0, ..., n) is the value of the function on an input vector with i ones.
Properties
- A restricted Boltzman machine with [math]n[/math] input units and [math]n^2+1[/math] hidden units can represent any symmetric Boolean function. [1]
- A symmetric function has nearest neighbor complexity bounded by [math]NN(f) \leq n+1[/math]. [2]
Examples
TODO: this was taken from Wikipedia. Please create the function pages for these functions, add the symmetric category tag to them, and then delete them from the examples list.
- Threshold functions: their value is 1 on input vectors with k or more ones for a fixed k
- Exact-value functions: their value is 1 on input vectors with k ones for a fixed k
- Counting functions : their value is 1 on input vectors with the number of ones congruent to k mod m for fixed k, m
References
- ↑ Theorem 7 in James Martens, Arkadev Chattopadhyay, Toniann Pitassi, Richard Zemel, On the Representational Efficiency of Restricted Boltzmann Machines, NIPS 2013
- ↑ Péter Hajnal, Zhihao Liu, György Turán, Nearest neighbor representations of Boolean functions, Proposition 3
Pages in category "Symmetric function"
The following 4 pages are in this category, out of 4 total.
