Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR02-069 | 12th June 2004 00:00

RSS-Feed




Revision #1
Authors: Luca Trevisan
Accepted on: 12th June 2004 00:00
Downloads: 1912
Keywords: 


Abstract:


Paper:

TR02-069 | 14th November 2002 00:00

A Note on Deterministic Approximate Counting for k-DNF





TR02-069
Authors: Luca Trevisan
Publication: 10th December 2002 21:33
Downloads: 1524
Keywords: 


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.



ISSN 1433-8092 | Imprint