Rademacher averages and phase transitions in Glivenko-Cantelli classes.
Shahar MendelsonPublished in: IEEE Trans. Inf. Theory (2002)
Keyphrases
- phase transition
- random constraint satisfaction problems
- constraint satisfaction
- satisfiability problem
- term dnf
- data dependent
- np complete
- randomly generated
- random instances
- combinatorial problems
- graph coloring
- cellular automata
- hard problems
- sat problem
- constraint satisfaction problems
- risk bounds
- learning algorithm