A Switching Lemma for Small Restrictions and Lower Bounds for k - DNF Resolution.

Nathan Segerlind Samuel R. Buss Russell Impagliazzo

Published in: FOCS (2002)

Keyphrases

lower bound
upper bound
branch and bound algorithm
high resolution
branch and bound
learning algorithm
boolean functions
uniform distribution
np hard
low resolution
objective function
optimal solution
worst case
linear programming
vc dimension
max sat