A phase transition for the uniform distribution in the pattern maximum likelihood problem.
Winston FernandesNavin KashyapPublished in: ITW (2013)
Keyphrases
- uniform distribution
- phase transition
- maximum likelihood
- term dnf
- boolean functions
- constraint satisfaction
- pac learning
- randomly generated
- satisfiability problem
- np complete
- hard problems
- monotone boolean functions
- random constraint satisfaction problems
- pattern matching
- random instances
- membership queries
- gaussian distribution
- sat problem
- relational learning
- cellular automata
- dnf formulas
- multi class
- np complete problems
- agnostic learning