Low-degree phase transitions for detecting a planted clique in sublinear time.
Jay MardiaKabir Aladin VerchandAlexander S. WeinPublished in: COLT (2024)
Keyphrases
- phase transition
- low degree
- term dnf
- constraint satisfaction
- random constraint satisfaction problems
- satisfiability problem
- np complete
- hard problems
- random instances
- decision lists
- graph coloring
- np complete problems
- random graphs
- sat problem
- randomly generated
- cellular automata
- uniform distribution
- relational learning
- sat instances
- decision trees
- orders of magnitude
- multi class
- search algorithm