A Non-linear Time Lower Bound for Boolean Branching Programs.
Miklós AjtaiPublished in: Theory Comput. (2005)
Keyphrases
- concept learning
- lower bound
- worst case
- upper bound
- branch and bound
- branch and bound algorithm
- real valued
- boolean functions
- np hard
- lower and upper bounds
- objective function
- optimal solution
- lower bounding
- average case
- polynomial approximation
- linear programming relaxation
- competitive ratio
- sufficiently accurate
- sample complexity
- theoretical analysis