Difference between revisions of "Main Page"
m (→Properties of Boolean functions) |
m (→Misc Topics) |
||
| (60 intermediate revisions by 2 users not shown) | |||
| Line 1: | Line 1: | ||
== Introduction == | == Introduction == | ||
| − | Welcome to the Boolean Zoo! | + | Welcome to the '''Boolean Zoo'''! |
A Boolean function is a function <math>f:\{-1,1\}^n \to \{-1,1\}</math>. | A Boolean function is a function <math>f:\{-1,1\}^n \to \{-1,1\}</math>. | ||
| − | Inspired by the [https://complexityzoo.uwaterloo.ca/Complexity_Zoo ComplexityZoo], the purpose of this wiki is to serve as a repository for examples and counterexamples in Boolean analysis. Ideally, each function page should briefly describe the function, and give a comprehensive list of all (interesting) known results about that function, together with a citation / link to that result. It should also give a comprehensive list of interesting results which are ''not'' known (aka "open problems"). | + | Inspired by the [https://complexityzoo.uwaterloo.ca/Complexity_Zoo ComplexityZoo], the purpose of this wiki is to serve as a repository for examples and counterexamples in Boolean analysis. Ideally, each function page should briefly describe the function, and give a comprehensive list of all (interesting) known results about that function, together with a citation / link to that result. It should also give a comprehensive list of interesting results which are ''not'' known (aka "open problems"). |
| − | The Boolean Zoo is a collaborative project, and you yourself are one of the collaborators. Do you know of a function or property that isn't on the list? Add it! Did you prove, discover, or stumble upon an interesting theorem regarding a Boolean function? Cite it! | + | Types of results that are of interest to this wiki include, but are not limited to: |
| + | * Bounds and calculation of Fourier coefficients | ||
| + | * Complexity of computation by various computational models | ||
| + | * Query complexity and property testing | ||
| + | * Information and functional inequalities | ||
| + | * Noise sensitivity and stability | ||
| + | * Whether the function is an extremal object of some property | ||
| + | * Counting and enumeration | ||
| + | * Comparison between different functions. | ||
| + | |||
| + | The Boolean Zoo is a collaborative project, and you yourself are one of the collaborators. Do you know of a function or property that isn't on the list? Add it! Did you prove, discover, or stumble upon an interesting theorem regarding a Boolean function? Cite it! You should read the [[Boolean Zoo:Editing guidelines|editing guidelines]]. | ||
=== Contact === | === Contact === | ||
The zoo is currently owned and maintained by [http://www.wisdom.weizmann.ac.il/~renang/ Renan Gross], who can be contacted at renan.gross ~at~ weizmann.ac.il | The zoo is currently owned and maintained by [http://www.wisdom.weizmann.ac.il/~renang/ Renan Gross], who can be contacted at renan.gross ~at~ weizmann.ac.il | ||
| + | The zoo is currently unable to send emails. Please contact Renan for administrative and technical issues. | ||
=== Difference from Wikipedia === | === Difference from Wikipedia === | ||
As an encyclopedia, Wikipedia is great at giving a general overview of common functions and terms, but cannot delve into the details and results that are sometimes needed for research. The Boolean Zoo, on the other hand, will happily accept even the most exotic and niche of functions. | As an encyclopedia, Wikipedia is great at giving a general overview of common functions and terms, but cannot delve into the details and results that are sometimes needed for research. The Boolean Zoo, on the other hand, will happily accept even the most exotic and niche of functions. | ||
| + | |||
| + | === Difference from "Analysis of Boolean functions" === | ||
| + | This Boolean Zoo is a repository and not a textbook. It therefore supplements, rather than competes, with O'Donnell's "[http://www.math.tau.ac.il/~amnon/Classes/2016-PRG/Analysis-Of-Boolean-Functions.pdf Analysis of Boolean functions]", as it contains no proofs and is intended to serve as a starting point for conjectures, examples and counterexamples. With hope, its open, online editing will allow it to be updated faster than traditional publishing. | ||
== Boolean functions == | == Boolean functions == | ||
* [[Address]] | * [[Address]] | ||
| − | * [[ | + | ** [[Wegener's monotone address]] |
| + | * [[Andreev's function]] | ||
| + | ** [[Generalized Andreev's function]] | ||
| + | * [[Chakraborty's function]] | ||
| + | * [[Clique containment]] | ||
| + | * [[Cube]] | ||
* [[Dictator]] | * [[Dictator]] | ||
| + | * [[DNF]] | ||
* [[Inner product]] | * [[Inner product]] | ||
* [[Iterated majority]] | * [[Iterated majority]] | ||
| + | * [[Iterated nand]] | ||
* [[Junta]] | * [[Junta]] | ||
| + | * [[Linear threshold]] | ||
* [[Majority]] | * [[Majority]] | ||
| − | * [[ | + | * [[Mod q]] |
* [[Parity]] | * [[Parity]] | ||
| + | * [[Perceptron]] | ||
* [[Percolation crossing]] | * [[Percolation crossing]] | ||
| − | * [[ | + | ** [[Extended butterfly percolation]] |
* [[Polynomial]] | * [[Polynomial]] | ||
| + | * [[Polynomial threshold]] | ||
| + | * [[Rolling parity]] | ||
| + | * [[Runs]] | ||
| + | * [[Rubinstein's sensitivity function]] | ||
* [[Tribes]] | * [[Tribes]] | ||
| + | ** [[Generalized Tribes]] | ||
| + | * [[Savicky's function]] | ||
| + | * [[Sipser's function]] | ||
| + | |||
| + | == Categories of Boolean functions == | ||
| + | * [[:Category:Balanced function|Balanced]] | ||
| + | * [[:Category:Biased function|Biased]] | ||
| + | * [[:Category:Evasive function|Evasive]] | ||
| + | * [[:Category:even function|Even]] | ||
| + | * [[:Category:Locally biased function|Locally biased]] | ||
| + | * [[:Category:Locally stable function|Locally stable]] | ||
| + | * [[:Category:Monotone function|Monotone]] | ||
| + | * [[:Category:Noise sensitive function|Noise sensitive]] | ||
| + | * [[:Category:Noise stable function|Noise stable]] | ||
| + | * [[:Category:odd function|Odd]] | ||
| + | * [[:Category:Symmetric function|Symmetric]] | ||
| + | * [[:Category:Transitive-symmetric function|Transitive symmetric]] | ||
| − | == | + | == Misc Topics == |
| − | * [[ | + | *[[Circuit complexity]] |
| − | * [[Influence]] | + | *[[Decision tree complexity]] |
| − | * [[ | + | *[[Fourier representation]] |
| − | * [[ | + | *[[Functional inequalities]] |
| − | * [[ | + | *[[Influence]] |
| − | * [[ | + | *[[Nearest neighbor representation]] |
| − | * [[ | + | *[[Noise sensitivity]] |
| + | *[[Noise stability]] | ||
| + | *[[Partition size]] | ||
| + | *[[Resilience]] | ||
| + | *[[Revealment]] | ||
| + | *[[Sensitivity]] | ||
| + | *[[Volatility]] | ||
Latest revision as of 10:05, 20 March 2022
Contents
Introduction
Welcome to the Boolean Zoo!
A Boolean function is a function [math]f:\{-1,1\}^n \to \{-1,1\}[/math].
Inspired by the ComplexityZoo, the purpose of this wiki is to serve as a repository for examples and counterexamples in Boolean analysis. Ideally, each function page should briefly describe the function, and give a comprehensive list of all (interesting) known results about that function, together with a citation / link to that result. It should also give a comprehensive list of interesting results which are not known (aka "open problems").
Types of results that are of interest to this wiki include, but are not limited to:
- Bounds and calculation of Fourier coefficients
- Complexity of computation by various computational models
- Query complexity and property testing
- Information and functional inequalities
- Noise sensitivity and stability
- Whether the function is an extremal object of some property
- Counting and enumeration
- Comparison between different functions.
The Boolean Zoo is a collaborative project, and you yourself are one of the collaborators. Do you know of a function or property that isn't on the list? Add it! Did you prove, discover, or stumble upon an interesting theorem regarding a Boolean function? Cite it! You should read the editing guidelines.
Contact
The zoo is currently owned and maintained by Renan Gross, who can be contacted at renan.gross ~at~ weizmann.ac.il The zoo is currently unable to send emails. Please contact Renan for administrative and technical issues.
Difference from Wikipedia
As an encyclopedia, Wikipedia is great at giving a general overview of common functions and terms, but cannot delve into the details and results that are sometimes needed for research. The Boolean Zoo, on the other hand, will happily accept even the most exotic and niche of functions.
Difference from "Analysis of Boolean functions"
This Boolean Zoo is a repository and not a textbook. It therefore supplements, rather than competes, with O'Donnell's "Analysis of Boolean functions", as it contains no proofs and is intended to serve as a starting point for conjectures, examples and counterexamples. With hope, its open, online editing will allow it to be updated faster than traditional publishing.
Boolean functions
- Address
- Andreev's function
- Chakraborty's function
- Clique containment
- Cube
- Dictator
- DNF
- Inner product
- Iterated majority
- Iterated nand
- Junta
- Linear threshold
- Majority
- Mod q
- Parity
- Perceptron
- Percolation crossing
- Polynomial
- Polynomial threshold
- Rolling parity
- Runs
- Rubinstein's sensitivity function
- Tribes
- Savicky's function
- Sipser's function
Categories of Boolean functions
- Balanced
- Biased
- Evasive
- Even
- Locally biased
- Locally stable
- Monotone
- Noise sensitive
- Noise stable
- Odd
- Symmetric
- Transitive symmetric
