Difference between revisions of "Main Page"
m (→Boolean functions) |
m (→Boolean functions) |
||
| Line 26: | Line 26: | ||
== Boolean functions == | == Boolean functions == | ||
* [[Address]] | * [[Address]] | ||
| + | * [[Andreev's function]] | ||
* [[Dictator]] | * [[Dictator]] | ||
* [[Inner product]] | * [[Inner product]] | ||
| Line 37: | Line 38: | ||
* [[Polynomial]] | * [[Polynomial]] | ||
* [[Tribes]] | * [[Tribes]] | ||
| − | * [[Generalized Tribes]] | + | ** [[Generalized Tribes]] |
* [[Wegners monotone address | Wegner's monotone address]] | * [[Wegners monotone address | Wegner's monotone address]] | ||
Revision as of 07:17, 30 September 2018
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
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.
Boolean functions
- Address
- Andreev's function
- Dictator
- Inner product
- Iterated majority
- Junta
- Majority
- Mod q
- Parity
- Percolation crossing
- Perceptron
- Polynomial
- Tribes
- Wegner's monotone address
