On the Power of Adaptivity in Sparse Recovery
From MaRDI portal
Publication:5495018
DOI10.1109/FOCS.2011.83zbMath1292.94012arXiv1110.3850OpenAlexW2168831133MaRDI QIDQ5495018
David P. Woodruff, Eric Price, Piotr Indyk
Publication date: 30 July 2014
Published in: 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1110.3850
Analysis of algorithms and problem complexity (68Q25) Sampling theory in information and communication theory (94A20)
Related Items (9)
An adaptivity hierarchy theorem for property testing ⋮ An Optimal Approximation for Submodular Maximization Under a Matroid Constraint in the Adaptive Complexity Model ⋮ Improved Algorithms for Adaptive Compressed Sensing ⋮ Algorithms for cardinality-constrained monotone DR-submodular maximization with low adaptivity and query complexity ⋮ On Low-Risk Heavy Hitters and Sparse Recovery Schemes ⋮ Querying a Matrix Through Matrix-Vector Products. ⋮ Fast algorithms for supermodular and non-supermodular minimization via bi-criteria strategy ⋮ An adaptive algorithm for maximization of non-submodular function with a matroid constraint ⋮ Unnamed Item
This page was built for publication: On the Power of Adaptivity in Sparse Recovery
