The Complexity of Somewhat Approximation Resistant Predicates.

Subhash Khot Madhur Tulsiani Pratik Worah

Published in: Electron. Colloquium Comput. Complex. (2012)

Keyphrases

approximation error
error tolerance
space complexity
artificial intelligence
computer vision
multiscale
computational complexity
computational cost
worst case
greedy algorithm
horn clauses
decision problems
efficient computation