Consider any Boolean function F(X_1,\ldots,X_N) that has more than 2^{-N^{d}} satisfying assignments and that can be expressed by a CNF formula with at most N^{1+e} clauses for some d>0 and e>0 such that d+e is less than 1 (*). Then how many variables do we need to fix in order ... more >>>