Querying a Matrix Through Matrix-Vector Products.

DOI10.4230/LIPIcs.ICALP.2019.94OpenAlexW2965571888MaRDI QIDQ5091255

David P. Woodruff, Xiaoming Sun, Guang Yang, Jia-Lin Zhang

Publication date: 21 July 2022

Full work available at URL: https://doi.org/10.4230/LIPIcs.ICALP.2019.94

zbMATH Keywords

sketchinglinear algebracommunication complexity

Mathematics Subject Classification ID

Theory of computing (68Qxx) Theory of software (68Nxx)

Related Items

Almost optimal query algorithm for hitting set using a subset query ⋮ Vector-Matrix-Vector Queries for Solving Linear Algebra, Statistics, and Graph Problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Property testing lower bounds via communication complexity
• Computational Advertising: Techniques for Targeting Relevant Ads
• Single Pass Spectral Sparsification in Dynamic Streams
• Maximum Matching in Turnstile Streams
• Maximum Matchings in Dynamic Graph Streams and the Simultaneous Communication Model
• On Estimating Maximum Matching Size in Graph Streams
• Approximately Counting Triangles in Sublinear Time
• Improved Algorithms for Adaptive Compressed Sensing
• Embeddings of Schatten Norms with Applications to Data Streams
• Near-optimal linear decision trees for k-SUM and related problems
• Testing Matrix Rank, Optimally
• Adaptive Sparse Recovery with Limited Adaptivity
• Turnstile streaming algorithms might as well be linear sketches
• On approximating functions of the singular values in a stream
• On Sketching Matrix Norms and the Top Singular Vector
• Lower Bounds for Sparse Recovery
• Stable signal recovery from incomplete and inaccurate measurements
• On the Power of Adaptivity in Sparse Recovery
• Lower Bounds for Adaptive Sparse Recovery
• On the singular values of Gaussian random matrices

This page was built for publication: Querying a Matrix Through Matrix-Vector Products.