{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,6]],"date-time":"2026-04-06T19:20:51Z","timestamp":1775503251080,"version":"3.50.1"},"reference-count":42,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2021,10,4]],"date-time":"2021-10-04T00:00:00Z","timestamp":1633305600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"crossref","award":["61832003, 61872334"],"award-info":[{"award-number":["61832003, 61872334"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Strategic Priority Research Program of Chinese Academy of Sciences","award":["XDA27000000"],"award-info":[{"award-number":["XDA27000000"]}]},{"name":"National Science Foundation","award":["CCF-181584"],"award-info":[{"award-number":["CCF-181584"]}]},{"name":"Chinese Academy of Sciences and the Simons Institute for the Theory of Computing"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2021,10,31]]},"abstract":"<jats:p>\n            We consider algorithms with access to an unknown matrix M \u03b5 F\n            <jats:sup>n\u00d7d<\/jats:sup>\n            via\n            <jats:italic>matrix-vector products<\/jats:italic>\n            , namely, the algorithm chooses vectors v\n            <jats:sup>1<\/jats:sup>\n            , \u20db , v\n            <jats:sup>q<\/jats:sup>\n            , and observes Mv\n            <jats:sup>1<\/jats:sup>\n            , \u20db , Mv\n            <jats:sup>q<\/jats:sup>\n            . Here the v\n            <jats:sup>i<\/jats:sup>\n            can be randomized as well as chosen adaptively as a function of Mv\n            <jats:sup>1<\/jats:sup>\n            , \u20db , Mv\n            <jats:sup>i-1<\/jats:sup>\n            . Motivated by applications of sketching in distributed computation, linear algebra, and streaming models, as well as connections to areas such as communication complexity and property testing, we initiate the study of the number\n            <jats:italic>q<\/jats:italic>\n            of queries needed to solve various fundamental problems. We study problems in three broad categories, including linear algebra, statistics problems, and graph problems. For example, we consider the number of queries required to approximate the rank, trace, maximum eigenvalue, and norms of a matrix M; to compute the AND\/OR\/Parity of each column or row of M, to decide whether there are identical columns or rows in M or whether M is symmetric, diagonal, or unitary; or to compute whether a graph defined by M is connected or triangle-free. We also show separations for algorithms that are allowed to obtain matrix-vector products only by querying vectors on the right, versus algorithms that can query vectors on both the left and the right. We also show separations depending on the underlying field the matrix-vector product occurs in. For graph problems, we show separations depending on the form of the matrix (bipartite adjacency versus signed edge-vertex incidence matrix) to represent the graph.\n          <\/jats:p>\n          <jats:p>Surprisingly, very few works discuss this fundamental model, and we believe a thorough investigation of problems in this model would be beneficial to a number of different application areas.<\/jats:p>","DOI":"10.1145\/3470566","type":"journal-article","created":{"date-parts":[[2021,10,5]],"date-time":"2021-10-05T01:10:42Z","timestamp":1633396242000},"page":"1-19","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":12,"title":["Querying a Matrix through Matrix-Vector Products"],"prefix":"10.1145","volume":"17","author":[{"given":"Xiaoming","family":"Sun","sequence":"first","affiliation":[{"name":"Institute of Computing Technology, Chinese Academy of Sciences, China and University of Chinese Academy of Sciences, Beijing, China"}]},{"given":"David P.","family":"Woodruff","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, Pennsylvania, USA"}]},{"given":"Guang","family":"Yang","sequence":"additional","affiliation":[{"name":"Institute of Computing Technology, Chinese Academy of Sciences, China and Conflux, Beijing, China"}]},{"given":"Jialin","family":"Zhang","sequence":"additional","affiliation":[{"name":"Institute of Computing Technology, Chinese Academy of Sciences, China and University of Chinese Academy of Sciences, Beijing, China"}]}],"member":"320","published-online":{"date-parts":[[2021,10,4]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973099.40"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.5555\/2982445.2982465"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/237814.237823"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974782.113"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974331.ch93"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1944345.1944349"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973075.95"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.46"},{"key":"e_1_2_1_9_1","volume-title":"Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201902)","author":"Bar-Yossef Ziv","year":"2002"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/129712.129730"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-012-0040-x"},{"key":"e_1_2_1_12_1","volume-title":"Proceedings of the Conference on Learning Theory (COLT\u201920)","author":"Braverman Mark","year":"2020"},{"key":"e_1_2_1_13_1","volume-title":"Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsm\u00e4ssan","author":"Braverman Vladimir","year":"2018"},{"key":"e_1_2_1_14_1","volume-title":"Stable signal recovery from incomplete and inaccurate measurements. Communications on Pure and Applied Mathematics: A Journal Issued by the Courant Institute of Mathematical Sciences 59, 8","author":"Candes J","year":"2006"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2015.2391251"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/15M1054389"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/070683155"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-31594-7_38"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.83"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.169"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188770"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.5555\/3235586.3235594"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1137\/141002281"},{"key":"e_1_2_1_24_1","volume-title":"Aspects of multivariate statistical theory.The Statistician 33, 2","author":"Kent T.","year":"1984"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-48350-3_70"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973402.114"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591812"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897581"},{"key":"e_1_2_1_29_1","volume-title":"Schatten norms, and subspace embeddings.RANDOM\/APPROX 2016 60, 39","author":"Li Yi","year":"2016"},{"key":"e_1_2_1_30_1","volume-title":"Proceedings of the 44th International Colloquium on Automata, Languages, and Programming (ICALP\u201917)","author":"Li Yi","year":"2017"},{"key":"e_1_2_1_31_1","volume-title":"Proceedings of the 28th International Conference on Neural Information Processing Systems (NIPS\u201915)","author":"Musco Cameron","year":"2015"},{"key":"e_1_2_1_32_1","first-page":"1","article-title":"Improved algorithms for adaptive compressed sensing. In Proceedings of the 45th International Colloquium on Automata, Languages, and Programming (ICALP\u201918) (July 9\u201313, 2018, Prague","volume":"90","author":"Nakos Vasileios","year":"2018","journal-title":"Czech Republic)."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973105.47"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0024-3795(00)00322-0"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188796"},{"key":"e_1_2_1_36_1","volume-title":"Proceedings of the 46th International Colloquium on Automata, Languages, and Programming (ICALP\u201919)","author":"Sun Xiaoming","year":"2019"},{"key":"e_1_2_1_37_1","volume-title":"Introduction to the non-asymptotic analysis of random matrices. Compressed Sensing: Theory and Applications (11","author":"Vershynin Roman","year":"2010"},{"key":"e_1_2_1_38_1","unstructured":"Martin Wainwright. High-dimensional statistics: A non-asymptotic viewpoint. https:\/\/www.stat.berkeley.edu\/~mjwain\/stat210b\/Chap2_TailBounds_Jan22_2015.pdf.  Martin Wainwright. High-dimensional statistics: A non-asymptotic viewpoint. https:\/\/www.stat.berkeley.edu\/~mjwain\/stat210b\/Chap2_TailBounds_Jan22_2015.pdf."},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01456804"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1561\/0400000060"},{"key":"e_1_2_1_41_1","volume-title":"Proceedings of the 18th Annual Symposium on Foundations of Computer Science (FOCS\u201977)","author":"Chi-Chin Yao Andrew","year":"1977"},{"key":"e_1_2_1_42_1","unstructured":"Qiaochu Yuan. 2017. Singular value decomposition. (2017). https:\/\/qchu.wordpress.com\/2017\/03\/13\/singular-value-decomposition\/.  Qiaochu Yuan. 2017. Singular value decomposition. (2017). https:\/\/qchu.wordpress.com\/2017\/03\/13\/singular-value-decomposition\/."}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3470566","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3470566","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3470566","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:18:54Z","timestamp":1750191534000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3470566"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,10,4]]},"references-count":42,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2021,10,31]]}},"alternative-id":["10.1145\/3470566"],"URL":"https:\/\/doi.org\/10.1145\/3470566","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,10,4]]},"assertion":[{"value":"2020-02-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-06-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-10-04","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}