White-Box vs. Black-Box Complexity of Search Problems: Ramsey and Graph Property Testing.
Ilan KomargodskiMoni NaorEylon YogevPublished in: FOCS (2017)
Keyphrases
- white box
- black box
- search problems
- graph search
- search algorithm
- orders of magnitude
- test cases
- heuristic search
- black boxes
- hybrid systems
- search strategies
- integration testing
- test data
- white box testing
- source code
- search space
- computational complexity
- constraint satisfaction problems
- upper bound
- optimal solution
- high level