---
_id: '11868'
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."
article_number: 21-30
article_processing_charge: No
arxiv: 1
author:
- first_name: Monika H
  full_name: Henzinger, Monika H
  id: 540c9bbd-f2de-11ec-812d-d04a5be85630
  last_name: Henzinger
  orcid: 0000-0002-5008-6530
- first_name: Sebastian
  full_name: Krinninger, Sebastian
  last_name: Krinninger
- first_name: Danupon
  full_name: Nanongkai, Danupon
  last_name: Nanongkai
- first_name: Thatchaphol
  full_name: Saranurak, Thatchaphol
  last_name: Saranurak
citation:
  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>'
  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.
  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.'
  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>.
  short: M.H. Henzinger, S. Krinninger, D. Nanongkai, T. Saranurak, in:, 47th Annual
    ACM Symposium on Theory of Computing, Association for Computing Machinery, 2015.
conference:
  end_date: 2015-06-17
  location: Portland, OR, United States
  name: 'STOC: Symposium on Theory of Computing'
  start_date: 2015-06-14
date_created: 2022-08-16T09:31:21Z
date_published: 2015-06-14T00:00:00Z
date_updated: 2023-02-17T11:09:54Z
day: '14'
doi: 10.1145/2746539.2746609
extern: '1'
external_id:
  arxiv:
  - '1511.06773'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://arxiv.org/abs/1511.06773
month: '06'
oa: 1
oa_version: Preprint
publication: 47th Annual ACM Symposium on Theory of Computing
publication_identifier:
  isbn:
  - 978-145033536-2
  issn:
  - '0737.8017'
publication_status: published
publisher: Association for Computing Machinery
quality_controlled: '1'
scopus_import: '1'
status: public
title: Unifying and strengthening hardness for dynamic problems via the online matrix-vector
  multiplication conjecture
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2015'
...
---
_id: '11869'
abstract:
- lang: eng
  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."
article_processing_charge: No
arxiv: 1
author:
- first_name: Sayan
  full_name: Bhattacharya, Sayan
  last_name: Bhattacharya
- first_name: Monika H
  full_name: Henzinger, Monika H
  id: 540c9bbd-f2de-11ec-812d-d04a5be85630
  last_name: Henzinger
  orcid: 0000-0002-5008-6530
- first_name: Danupon
  full_name: Nanongkai, Danupon
  last_name: Nanongkai
- first_name: Charalampos
  full_name: Tsourakakis, Charalampos
  last_name: Tsourakakis
citation:
  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>'
  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>'
  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.
  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.
conference:
  end_date: 2015-06-17
  location: Portland, OR, United States
  name: 'STOC: Symposium on Theory of Computing'
  start_date: 2015-06-14
date_created: 2022-08-16T09:36:48Z
date_published: 2015-06-01T00:00:00Z
date_updated: 2023-02-17T11:17:03Z
day: '01'
doi: 10.1145/2746539.2746592
extern: '1'
external_id:
  arxiv:
  - '1504.02268'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://arxiv.org/abs/1504.02268
month: '06'
oa: 1
oa_version: Preprint
page: 173 - 182
publication: 47th Annual ACM Symposium on Theory of Computing
publication_identifier:
  isbn:
  - 978-145033536-2
  issn:
  - 0737-8017
publication_status: published
publisher: Association for Computing Machinery
quality_controlled: '1'
scopus_import: '1'
status: public
title: Space- and time-efficient algorithm for maintaining dense subgraphs on one-pass
  dynamic streams
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2015'
...