2026-07-24T10:25:21Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12629 2024-03-06T10:51:18Z ddc:004 open_access

Vector-Matrix-Vector Queries for Solving Linear Algebra, Statistics, and Graph Problems Rashtchian, Cyrus Woodruff, David P. Zhu, Hanlin Query complexity property testing vector-matrix-vector linear algebra statistics graph parameter estimation We consider the general problem of learning about a matrix through vector-matrix-vector queries. These queries provide the value of u^{T}Mv over a fixed field 𝔽 for a specified pair of vectors u,v ∈ 𝔽ⁿ. To motivate these queries, we observe that they generalize many previously studied models, such as independent set queries, cut queries, and standard graph queries. They also specialize the recently studied matrix-vector query model. Our work is exploratory and broad, and we provide new upper and lower bounds for a wide variety of problems, spanning linear algebra, statistics, and graphs. Many of our results are nearly tight, and we use diverse techniques from linear algebra, randomized algorithms, and communication complexity. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Cyrus Rashtchian and David P. Woodruff and Hanlin Zhu 2020 Is Part Of LIPIcs, Volume 176, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX/RANDOM.2020.26 urn:nbn:de:0030-drops-126294 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2020.26 eng https://creativecommons.org/licenses/by/3.0/legalcode