Lower Bounds for DNF-Refutations of a Relativized Weak Pigeonhole Principle.

Albert Atserias Moritz Müller Sergi Oliva

Published in: Electron. Colloquium Comput. Complex. (2013)

Keyphrases

lower bound
upper bound
branch and bound algorithm
uniform distribution
learning algorithm
branch and bound
boolean functions

np hard
objective function
membership queries
max sat
upper and lower bounds
vc dimension
worst case

lower and upper bounds
dnf formulas
equivalence queries
quadratic assignment problem
pac learning
learning theory

linear programming
machine learning
concept class
optimal solution
statistical queries
sample size