Sparse approximation is provably hard under coherent dictionaries
详细信息 查看全文
- 作者：A. Ç ; ivril ; ali.civril@antalya.edu.tr" class="auth_mail" title="E-mail the corresponding author
- 关键词：Sparse approximation ; Complexity ; PCP ; Unique games
- 刊名：Journal of Computer and System Sciences
- 出版年：2017
- 出版时间：March 2017
- 年：2017
- 卷：84
- 期：Complete
- 页码：32-43
- 全文大小：416 K
文摘
- •
Sparse approximation is hard even under reasonably coherent dictionaries.
- •
Previously, only NP-hardness was known in the general case.
- •
Two hardness assumptions used: P≠NP, Unique Games Conjecture.
- •
A new simple multilayered PCP is used.