Stronger Lower Bounds and Randomness-Hardness Tradeoffs using Associated Algebraic Complexity Classes.
Maurice J. JansenRahul SanthanamPublished in: Electron. Colloquium Comput. Complex. (2011)
Keyphrases
- lower bound
- worst case
- complexity measures
- computational complexity
- upper bound
- tractable cases
- np hard
- np hardness
- learning theory
- objective function
- vc dimension
- branch and bound
- random instances
- phase transition
- error bounds
- average case complexity
- algebraic structures
- data sets
- branch and bound algorithm
- decision problems
- neural network