Main Page

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").

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!

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
• And
• Dictator
• Inner product
• Iterated majority
• Junta
• Majority
• Or
• Parity
• Percolation crossing
• Perceptron
• Polynomial
• Tribes

Properties of Boolean functions

• Bias
• Local bias
• Local stability
• Monotone
• Noise sensitivity
• Symmetric

Misc Topics

• Fourier representation
• Stability
• Influence