[{"publisher":"Association for Computing Machinery","quality_controlled":"1","title":"Unifying and strengthening hardness for dynamic problems via the online matrix-vector multiplication conjecture","publication_status":"published","article_processing_charge":"No","date_created":"2022-08-16T09:31:21Z","author":[{"full_name":"Henzinger, Monika H","orcid":"0000-0002-5008-6530","last_name":"Henzinger","first_name":"Monika H","id":"540c9bbd-f2de-11ec-812d-d04a5be85630"},{"first_name":"Sebastian","last_name":"Krinninger","full_name":"Krinninger, Sebastian"},{"first_name":"Danupon","last_name":"Nanongkai","full_name":"Nanongkai, Danupon"},{"full_name":"Saranurak, Thatchaphol","first_name":"Thatchaphol","last_name":"Saranurak"}],"_id":"11868","scopus_import":"1","extern":"1","abstract":[{"lang":"eng","text":"Consider the following Online Boolean Matrix-Vector Multiplication problem: We are given an n x n matrix M and will receive n column-vectors of size n, denoted by v1, ..., vn, one by one. After seeing each vector vi, we have to output the product Mvi before we can see the next vector. A naive algorithm can solve this problem using O(n3) time in total, and its running time can be slightly improved to O(n3/log2 n) [Williams SODA'07]. We show that a conjecture that there is no truly subcubic (O(n3-ε)) time algorithm for this problem can be used to exhibit the underlying polynomial time hardness shared by many dynamic problems. For a number of problems, such as subgraph connectivity, Pagh's problem, d-failure connectivity, decremental single-source shortest paths, and decremental transitive closure, this conjecture implies tight hardness results. Thus, proving or disproving this conjecture will be very interesting as it will either imply several tight unconditional lower bounds or break through a common barrier that blocks progress with these problems. This conjecture might also be considered as strong evidence against any further improvement for these problems since refuting it will imply a major breakthrough for combinatorial Boolean matrix multiplication and other long-standing problems if the term \"combinatorial algorithms\" is interpreted as \"Strassen-like algorithms\" [Ballard et al. SPAA'11].\r\n\r\nThe conjecture also leads to hardness results for problems that were previously based on diverse problems and conjectures -- such as 3SUM, combinatorial Boolean matrix multiplication, triangle detection, and multiphase -- thus providing a uniform way to prove polynomial hardness results for dynamic algorithms; some of the new proofs are also simpler or even become trivial. The conjecture also leads to stronger and new, non-trivial, hardness results, e.g., for the fully-dynamic densest subgraph and diameter problems."}],"arxiv":1,"doi":"10.1145/2746539.2746609","day":"14","external_id":{"arxiv":["1511.06773"]},"date_updated":"2023-02-17T11:09:54Z","citation":{"ista":"Henzinger MH, Krinninger S, Nanongkai D, Saranurak T. 2015. Unifying and strengthening hardness for dynamic problems via the online matrix-vector multiplication conjecture. 47th Annual ACM Symposium on Theory of Computing. STOC: Symposium on Theory of Computing, 21–30.","short":"M.H. Henzinger, S. Krinninger, D. Nanongkai, T. Saranurak, in:, 47th Annual ACM Symposium on Theory of Computing, Association for Computing Machinery, 2015.","mla":"Henzinger, Monika H., et al. “Unifying and Strengthening Hardness for Dynamic Problems via the Online Matrix-Vector Multiplication Conjecture.” <i>47th Annual ACM Symposium on Theory of Computing</i>, 21–30, Association for Computing Machinery, 2015, doi:<a href=\"https://doi.org/10.1145/2746539.2746609\">10.1145/2746539.2746609</a>.","chicago":"Henzinger, Monika H, Sebastian Krinninger, Danupon Nanongkai, and Thatchaphol Saranurak. “Unifying and Strengthening Hardness for Dynamic Problems via the Online Matrix-Vector Multiplication Conjecture.” In <i>47th Annual ACM Symposium on Theory of Computing</i>. Association for Computing Machinery, 2015. <a href=\"https://doi.org/10.1145/2746539.2746609\">https://doi.org/10.1145/2746539.2746609</a>.","ieee":"M. H. Henzinger, S. Krinninger, D. Nanongkai, and T. Saranurak, “Unifying and strengthening hardness for dynamic problems via the online matrix-vector multiplication conjecture,” in <i>47th Annual ACM Symposium on Theory of Computing</i>, Portland, OR, United States, 2015.","ama":"Henzinger MH, Krinninger S, Nanongkai D, Saranurak T. Unifying and strengthening hardness for dynamic problems via the online matrix-vector multiplication conjecture. In: <i>47th Annual ACM Symposium on Theory of Computing</i>. Association for Computing Machinery; 2015. doi:<a href=\"https://doi.org/10.1145/2746539.2746609\">10.1145/2746539.2746609</a>","apa":"Henzinger, M. H., Krinninger, S., Nanongkai, D., &#38; Saranurak, T. (2015). Unifying and strengthening hardness for dynamic problems via the online matrix-vector multiplication conjecture. In <i>47th Annual ACM Symposium on Theory of Computing</i>. Portland, OR, United States: Association for Computing Machinery. <a href=\"https://doi.org/10.1145/2746539.2746609\">https://doi.org/10.1145/2746539.2746609</a>"},"year":"2015","conference":{"end_date":"2015-06-17","location":"Portland, OR, United States","name":"STOC: Symposium on Theory of Computing","start_date":"2015-06-14"},"language":[{"iso":"eng"}],"month":"06","article_number":"21-30","oa_version":"Preprint","publication":"47th Annual ACM Symposium on Theory of Computing","status":"public","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1511.06773"}],"oa":1,"publication_identifier":{"isbn":["978-145033536-2"],"issn":["0737.8017"]},"date_published":"2015-06-14T00:00:00Z","type":"conference"},{"language":[{"iso":"eng"}],"conference":{"location":"Portland, OR, United States","end_date":"2015-06-17","name":"STOC: Symposium on Theory of Computing","start_date":"2015-06-14"},"publication":"47th Annual ACM Symposium on Theory of Computing","oa_version":"Preprint","month":"06","main_file_link":[{"url":"https://arxiv.org/abs/1504.02268","open_access":"1"}],"status":"public","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","type":"conference","date_published":"2015-06-01T00:00:00Z","publication_identifier":{"issn":["0737-8017"],"isbn":["978-145033536-2"]},"oa":1,"quality_controlled":"1","page":"173 - 182","publisher":"Association for Computing Machinery","scopus_import":"1","_id":"11869","author":[{"full_name":"Bhattacharya, Sayan","last_name":"Bhattacharya","first_name":"Sayan"},{"full_name":"Henzinger, Monika H","orcid":"0000-0002-5008-6530","last_name":"Henzinger","first_name":"Monika H","id":"540c9bbd-f2de-11ec-812d-d04a5be85630"},{"full_name":"Nanongkai, Danupon","first_name":"Danupon","last_name":"Nanongkai"},{"full_name":"Tsourakakis, Charalampos","first_name":"Charalampos","last_name":"Tsourakakis"}],"article_processing_charge":"No","date_created":"2022-08-16T09:36:48Z","publication_status":"published","title":"Space- and time-efficient algorithm for maintaining dense subgraphs on one-pass dynamic streams","extern":"1","citation":{"chicago":"Bhattacharya, Sayan, Monika H Henzinger, Danupon Nanongkai, and Charalampos Tsourakakis. “Space- and Time-Efficient Algorithm for Maintaining Dense Subgraphs on One-Pass Dynamic Streams.” In <i>47th Annual ACM Symposium on Theory of Computing</i>, 173–82. Association for Computing Machinery, 2015. <a href=\"https://doi.org/10.1145/2746539.2746592\">https://doi.org/10.1145/2746539.2746592</a>.","ieee":"S. Bhattacharya, M. H. Henzinger, D. Nanongkai, and C. Tsourakakis, “Space- and time-efficient algorithm for maintaining dense subgraphs on one-pass dynamic streams,” in <i>47th Annual ACM Symposium on Theory of Computing</i>, Portland, OR, United States, 2015, pp. 173–182.","apa":"Bhattacharya, S., Henzinger, M. H., Nanongkai, D., &#38; Tsourakakis, C. (2015). Space- and time-efficient algorithm for maintaining dense subgraphs on one-pass dynamic streams. In <i>47th Annual ACM Symposium on Theory of Computing</i> (pp. 173–182). Portland, OR, United States: Association for Computing Machinery. <a href=\"https://doi.org/10.1145/2746539.2746592\">https://doi.org/10.1145/2746539.2746592</a>","ama":"Bhattacharya S, Henzinger MH, Nanongkai D, Tsourakakis C. Space- and time-efficient algorithm for maintaining dense subgraphs on one-pass dynamic streams. In: <i>47th Annual ACM Symposium on Theory of Computing</i>. Association for Computing Machinery; 2015:173-182. doi:<a href=\"https://doi.org/10.1145/2746539.2746592\">10.1145/2746539.2746592</a>","ista":"Bhattacharya S, Henzinger MH, Nanongkai D, Tsourakakis C. 2015. Space- and time-efficient algorithm for maintaining dense subgraphs on one-pass dynamic streams. 47th Annual ACM Symposium on Theory of Computing. STOC: Symposium on Theory of Computing, 173–182.","mla":"Bhattacharya, Sayan, et al. “Space- and Time-Efficient Algorithm for Maintaining Dense Subgraphs on One-Pass Dynamic Streams.” <i>47th Annual ACM Symposium on Theory of Computing</i>, Association for Computing Machinery, 2015, pp. 173–82, doi:<a href=\"https://doi.org/10.1145/2746539.2746592\">10.1145/2746539.2746592</a>.","short":"S. Bhattacharya, M.H. Henzinger, D. Nanongkai, C. Tsourakakis, in:, 47th Annual ACM Symposium on Theory of Computing, Association for Computing Machinery, 2015, pp. 173–182."},"year":"2015","date_updated":"2023-02-17T11:17:03Z","external_id":{"arxiv":["1504.02268"]},"day":"01","doi":"10.1145/2746539.2746592","arxiv":1,"abstract":[{"text":"While in many graph mining applications it is crucial to handle a stream of updates efficiently in terms of both time and space, not much was known about achieving such type of algorithm. In this paper we study this issue for a problem which lies at the core of many graph mining applications called densest subgraph problem. We develop an algorithm that achieves time- and space-efficiency for this problem simultaneously. It is one of the first of its kind for graph problems to the best of our knowledge.\r\n\r\nGiven an input graph, the densest subgraph is the subgraph that maximizes the ratio between the number of edges and the number of nodes. For any ε>0, our algorithm can, with high probability, maintain a (4+ε)-approximate solution under edge insertions and deletions using ~O(n) space and ~O(1) amortized time per update; here, $n$ is the number of nodes in the graph and ~O hides the O(polylog_{1+ε} n) term. The approximation ratio can be improved to (2+ε) with more time. It can be extended to a (2+ε)-approximation sublinear-time algorithm and a distributed-streaming algorithm. Our algorithm is the first streaming algorithm that can maintain the densest subgraph in one pass. Prior to this, no algorithm could do so even in the special case of an incremental stream and even when there is no time restriction. The previously best algorithm in this setting required O(log n) passes [BahmaniKV12]. The space required by our algorithm is tight up to a polylogarithmic factor.","lang":"eng"}]}]