Boolean circuits are a complexity
theoretic abstraction. A boolean circuit is an acyclic collection of
interconnected gates. Each gate computes a boolean function of 0, 1
or 2 single-bit inputs. A randomized boolean circuit takes a certain
number of random input bits in addition to its regular inputs.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
