## Approximating the Number of Satisfying Assignments in DNFs:
A Derandomization Challenge from the early-1990s

The challenge is to provide a (deterministic) polynomial-time algorithm
for approximating the number of satisfying assignments to a given DNF.
Indeed, this is a special case of approximating the number of satisfying
assignments to a given constant-depth Boolean circuit.
The latter task has a quasi-polynomial time (deterministic) algorithm,
whereas the bounds known for the DNF case are very close to being
polynomial. Still, the gap exists, and seems to be the first significant
step towards a full derandomization of BPP.

The state-of-the-art regarding deterministic approximation of DNFs
is provided by Luby and Velickovic's paper (of 23rd STOC, 1991).
This paper presents several interesting ideas,
but seems to utilize them to their very limits.
Later works on approximating the volume of combinatorial rectangles
are (at least) partially motivated by the DNF approximation problem,
but they typically lead to different directions
(which are of independent interest and are also clearly
relevant to the big challenge of derandomizing BPP).
Still, it seems good to try to revisit the DNF approximation problem.

**Update (May 15, 2012):** See choice 93.

Back to
list of Oded's choices.