Balanced Boolean function: Difference between revisions

Revision as of 04:30, 8 November 2009

Revision as of 23:11, 21 February 2010

Line 1:

In [[mathematics]] and [[computer science]], a '''balanced boolean function''' is a [[boolean function]] whose output yields as many 0s'''0'''s as 1s'''1'''s over its input set. This means that for a uniformly random input string of bits, the probability of getting a one is 1/2.

{{unreferenced|date=November 2009}}

In [[mathematics]], a '''balanced boolean function''' is a [[boolean function]] whose output yields as many 0s as 1s over its input set.

An example of a balanced boolean function is the function that assigns a '''1''' to every even number and '''0''' to all odd numbers (likewise the other way around). The same applies for functions assigning '''1''' to all positive numbers and '''0''' otherwise.

This means that for a uniformly random input string of bits, the probability of getting a one is 1/2.

== Usage ==

Balanced boolean functions are primarily used in cryptography.

== See also ==

* [[Bent function]]

== References ==

* [http://portal.acm.org/citation.cfm?id=1060627 Balanced boolean functions that can be evaluated so that every input bit is unlikely to be read], Annual ACM Symposium on Theory of Computing

{{math-stub}}