Hidden Cliques and the Certification of the Restricted Isometry Property

DOI10.1109/TIT.2014.2331341zbMath1360.94081arXiv1211.0665MaRDI QIDQ2986237

Anastasios Zouzias, Pascal Koiran

Publication date: 16 May 2017

Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1211.0665

Mathematics Subject Classification ID

Signal theory (characterization, reconstruction, filtering, etc.) (94A12) Image processing (compression, reconstruction, etc.) in information and communication theory (94A08)

Related Items (9)

Tensor clustering with planted structures: statistical optimality and computational limits ⋮ Multiple sparse measurement gradient reconstruction algorithm for DOA estimation in compressed sensing ⋮ Optimal detection of sparse principal components in high dimension ⋮ Non-Negative Sparse Regression and Column Subset Selection with L1 Error ⋮ A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem ⋮ The Average-Case Complexity of Counting Cliques in Erdös--Rényi Hypergraphs ⋮ Computing the spark: mixed-integer programming for the (vector) matroid girth problem ⋮ Planted Dense Subgraphs in Dense Random Graphs Can Be Recovered using Graph-based Machine Learning ⋮ Computational barriers in minimax submatrix detection

This page was built for publication: Hidden Cliques and the Certification of the Restricted Isometry Property