Bounded-Depth Frege Lower Bounds for Weaker Pigeonhole Principles.
Josh Buresh-OppenheimPaul BeameToniann PitassiRan RazAshish SabharwalPublished in: FOCS (2002)
Keyphrases
- lower bound
- upper bound
- branch and bound algorithm
- branch and bound
- depth map
- objective function
- lower and upper bounds
- optimal solution
- upper and lower bounds
- worst case
- depth information
- theoretical framework
- vc dimension
- optimal cost
- sample complexity
- neural network
- randomly generated problems
- expressive power
- constraint satisfaction problems
- np hard
- high resolution
- similarity measure
- image sequences