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.