It Was "All" for "Nothing": Sharp Phase Transitions for Noiseless Discrete Channels.
Jonathan Niles-WeedIlias ZadikPublished in: IEEE Trans. Inf. Theory (2023)
Keyphrases
- phase transition
- constraint satisfaction
- random constraint satisfaction problems
- satisfiability problem
- randomly generated
- hard problems
- combinatorial problems
- np complete
- noisy data
- cellular automata
- graph coloring
- random instances
- noisy images
- sat problem
- constraint satisfaction problems
- deep structure
- lower bound
- random graphs
- np complete problems
- boolean formulae