Lower bounds for Boolean formulae of depth 3 and the topology of the n-cube (preliminary version).
Klaus KriegelStephan WaackPublished in: FCT (1985)
Keyphrases
- preliminary version
- boolean formulae
- lower bound
- upper bound
- branch and bound algorithm
- branch and bound
- objective function
- lower and upper bounds
- boolean variables
- np hard
- upper and lower bounds
- vc dimension
- special case
- heuristic search
- expressive power
- learning algorithm
- learning theory
- sample complexity
- conjunctive normal form
- search algorithm