Lower Bound on Average-Case Complexity of Inversion of Goldreich's Function by Drunken Backtracking Algorithms.
Dmitry ItsyksonPublished in: Theory Comput. Syst. (2014)
Keyphrases
- lower bound
- average case complexity
- upper bound
- backtracking algorithms
- average case
- lower and upper bounds
- branch and bound algorithm
- objective function
- branch and bound
- constraint propagation
- worst case
- search algorithm
- optimal solution
- constraint networks
- np hard
- vc dimension
- constraint satisfaction problems
- upper and lower bounds