The Algorithmic Phase Transition of Random k-SAT for Low Degree Polynomials.
Guy BreslerBrice HuangPublished in: FOCS (2021)
Keyphrases
- phase transition
- low degree
- random instances
- randomly generated
- random constraint satisfaction problems
- satisfiability problem
- easy hard easy pattern
- sat problem
- random sat
- term dnf
- constraint satisfaction
- np complete problems
- stochastic local search
- hard problems
- graph coloring
- np complete
- boolean satisfiability
- sat instances
- combinatorial problems
- uniform distribution
- relational learning
- cellular automata
- davis putnam
- machine learning
- agnostic learning
- decision trees