Lower bounds for the complexity of linear functionals in the randomized setting.
Erich NovakHenryk WozniakowskiPublished in: J. Complex. (2011)
Keyphrases
- lower bound
- worst case
- upper bound
- linear complexity
- objective function
- randomized algorithms
- average case complexity
- complexity measures
- regret bounds
- linear systems
- np hard
- vc dimension
- neural network
- piecewise linear
- upper and lower bounds
- branch and bound algorithm
- linear constraints
- higher order
- quadratic assignment problem
- randomized algorithm
- computational cost
- special case