A Birthday Repetition Theorem and Complexity of Approximating Dense CSPs.

Pasin Manurangsi Prasad Raghavendra

Published in: ICALP (2017)

Keyphrases

constraint satisfaction problems
search space
constraint satisfaction
space complexity
search engine
knowledge base
database
information systems
computational complexity
computational cost
decision problems
memory requirements
constraint propagation
non binary