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