Difference between revisions of "Main Page"

From Boolean Zoo
Jump to: navigation, search
(Misc Topics)
m (Misc Topics)
 
(11 intermediate revisions by the same user not shown)
Line 24: Line 24:
 
=== 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]]
 
* [[Andreev's function]]
 
** [[Generalized Andreev's function]]
 
** [[Generalized Andreev's function]]
 +
* [[Chakraborty's function]]
 
* [[Clique containment]]
 
* [[Clique containment]]
 
* [[Cube]]
 
* [[Cube]]
Line 43: Line 48:
 
* [[Perceptron]]
 
* [[Perceptron]]
 
* [[Percolation crossing]]
 
* [[Percolation crossing]]
 +
** [[Extended butterfly percolation]]
 
* [[Polynomial]]
 
* [[Polynomial]]
 
* [[Polynomial threshold]]
 
* [[Polynomial threshold]]
 +
* [[Rolling parity]]
 
* [[Runs]]
 
* [[Runs]]
 +
* [[Rubinstein's sensitivity function]]
 
* [[Tribes]]
 
* [[Tribes]]
 
** [[Generalized Tribes]]
 
** [[Generalized Tribes]]
 
* [[Savicky's function]]
 
* [[Savicky's function]]
 
* [[Sipser's function]]
 
* [[Sipser's function]]
* [[Wegener's monotone address]]
 
  
 
== Categories of Boolean functions ==  
 
== Categories of Boolean functions ==  
 
* [[:Category:Balanced function|Balanced]]
 
* [[:Category:Balanced function|Balanced]]
 
* [[:Category:Biased function|Biased]]
 
* [[:Category:Biased function|Biased]]
 +
* [[:Category:Evasive function|Evasive]]
 
* [[:Category:even function|Even]]
 
* [[:Category:even function|Even]]
 
* [[:Category:Locally biased function|Locally biased]]
 
* [[:Category:Locally biased function|Locally biased]]
 
* [[:Category:Locally stable function|Locally stable]]
 
* [[:Category:Locally stable function|Locally stable]]
 
* [[:Category:Monotone function|Monotone]]
 
* [[:Category:Monotone function|Monotone]]
 +
* [[:Category:Noise sensitive function|Noise sensitive]]
 +
* [[:Category:Noise stable function|Noise stable]]
 
* [[:Category:odd function|Odd]]
 
* [[:Category:odd function|Odd]]
 
* [[:Category:Symmetric function|Symmetric]]
 
* [[:Category:Symmetric function|Symmetric]]
Line 65: Line 75:
 
== Misc Topics ==  
 
== Misc Topics ==  
 
*[[Circuit complexity]]
 
*[[Circuit complexity]]
*[[Decision tree]]
+
*[[Decision tree complexity]]
 
*[[Fourier representation]]
 
*[[Fourier representation]]
 
*[[Functional inequalities]]
 
*[[Functional inequalities]]
Line 73: Line 83:
 
*[[Noise stability]]
 
*[[Noise stability]]
 
*[[Partition size]]
 
*[[Partition size]]
 +
*[[Resilience]]
 
*[[Revealment]]
 
*[[Revealment]]
 
*[[Sensitivity]]
 
*[[Sensitivity]]
 
*[[Volatility]]
 
*[[Volatility]]

Latest revision as of 10:05, 20 March 2022

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

Categories of Boolean functions

Misc Topics