A Tight Lower Bound on Certificate Complexity in Terms of Block Sensitivity and Sensitivity.
Andris AmbainisKrisjanis PrusisPublished in: Electron. Colloquium Comput. Complex. (2014)
Keyphrases
- lower bound
- upper bound
- worst case
- branch and bound
- sensitivity analysis
- branch and bound algorithm
- objective function
- optimal solution
- high sensitivity
- np hard
- complexity analysis
- space complexity
- lower and upper bounds
- average case complexity
- database
- dct coefficients
- digital images
- computational complexity
- data sets