We prove that the exact versions of the domatic number problem are complete
for the levels of the boolean hierarchy over NP. The domatic number
problem, which arises in the area of computer networks, is the problem of
partitioning a given graph into a maximum number ... more >>>

In this paper we study the problem of approximating a boolean
function using the Hamming distance as the approximation measure.
Namely, given a boolean function f, its k-approximation is the
function f^k returning true on the same points in which f does,
plus all points whose Hamming distance from the ... more >>>

We consider the computational power of constant width polynomial
size cylindrical circuits and nondeterministic branching programs.
We show that every function computed by a Pi2 o MOD o AC0 circuit
can also be computed by a constant width polynomial size cylindrical
nondeterministic branching program (or cylindrical circuit) and
that ... more >>>