__
TR02-069 | 14th November 2002 00:00
__

#### A Note on Deterministic Approximate Counting for k-DNF

**Abstract:**
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

an additive error e.

For k-DNF, a multiplicative approximation is also achievable in

time polynomial in 1/e and linear in the size of f.

Previous algorithms achieved polynomial (but not linear)

dependency on the size of f and on 1/e; their dependency on k,

however, was much better than ours. Unlike previous algorithms,

our algorithm is not based on derandomization techniques, and it

is quite similar to an algorithm by Hirsch for the related problem

of solving k-SAT under the promise that an e-fraction of the

assignments are satisfying. Our analysis is different from (and

somewhat simpler than) Hirsch's.