Querying a Matrix Through Matrix-Vector Products.

DOI10.4230/LIPICS.ICALP.2019.94MaRDI QIDQ5091255zbMATH OpenOpenAlexFDO

Authors Xiaoming Sun, David P. Woodruff, Guang Yang, Jialin Zhang

Publication date 21 July 2022

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

zbMATH Keywords

communication complexitylinear algebrasketching

Mathematics Subject Classification ID

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

Recommendations

• Querying a Matrix through Matrix-Vector Products
• Testing matrix rank, optimally
• Fast Monte Carlo Algorithms for Matrices I: Approximating Matrix Multiplication
• Numerical linear algebra in the streaming model
• Compressed matrix multiplication

Cites work

• Adaptive sparse recovery with limited adaptivity
• Approximately counting triangles in sublinear time
• Embeddings of Schatten norms with applications to data streams
• scientific article; zbMATH DE number 1256715 (Why is no real title available?)
• scientific article; zbMATH DE number 7250148 (Why is no real title available?)
• scientific article; zbMATH DE number 6789285 (Why is no real title available?)
• Improved algorithms for adaptive compressed sensing
• Lower bounds for adaptive sparse recovery
• Lower bounds for sparse recovery
• Maximum matching in turnstile streams
• Maximum matchings in dynamic graph streams and the simultaneous communication model
• Near-optimal linear decision trees for k-SUM and related problems
• On approximating functions of the singular values in a stream
• On estimating maximum matching size in graph streams
• On sketching matrix norms and the top singular vector
• On the Power of Adaptivity in Sparse Recovery
• On the singular values of Gaussian random matrices
• Property testing lower bounds via communication complexity
• Single pass spectral sparsification in dynamic streams
• Sketching as a tool for numerical linear algebra
• Stable signal recovery from incomplete and inaccurate measurements
• Testing matrix rank, optimally
• Turnstile streaming algorithms might as well be linear sketches

Cited in

(7)

• Querying a Matrix through Matrix-Vector Products
• Vector-Matrix-Vector Queries for Solving Linear Algebra, Statistics, and Graph Problems
• Almost optimal query algorithm for hitting set using a subset query
• On the cut-query complexity of approximating max-cut
• Query lower bounds for log-concave sampling
• SNARK lower bounds via communication complexity
• Cut-query algorithms with few rounds

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5091255)