Sparsity according to Prony: Average-Case Performance Analysis and Phase Transition.
Yue M. LuJon OñativiaPier Luigi DragottiPublished in: CoRR (2016)
Keyphrases
- average case
- phase transition
- constraint satisfaction
- worst case
- uniform distribution
- satisfiability problem
- randomly generated
- np complete
- worst case analysis
- random instances
- random constraint satisfaction problems
- hard problems
- cellular automata
- np complete problems
- high dimensional
- average case complexity
- sat problem
- np hard
- vc dimension
- random graphs
- constraint satisfaction problems
- objective function
- sat instances