
PreviousNext
We describe a deterministic algorithm that, for constant k,
given a k-DNF or k-CNF formula f and a parameter e, runs in time
linear in the size of f and polynomial in 1/e and returns an
estimate of the fraction of satisfying assignments for f up to ...
more >>>
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 >>>
PreviousNext