Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Unifying and Strengthening Hardness for Dynamic Problems via the Online Matrix-Vector Multiplication Conjecture
University of Vienna, Austria.
University of Vienna, Austria.
KTH, School of Electrical Engineering and Computer Science (EECS), Theoretical Computer Science, TCS.ORCID iD: 0000-0003-4468-2675
KTH, School of Electrical Engineering and Computer Science (EECS), Theoretical Computer Science, TCS.ORCID iD: 0000-0003-3694-740X
2015 (English)In: Proceedings of the forty-seventh annual ACM symposium on Theory of computing, New York, NY, USA: ACM Digital Library, 2015, , p. 21-30p. 21-30Conference paper, Published paper (Refereed)
Abstract [en]

Consider the following Online Boolean Matrix- Vector Multiplication problem: We are given annxn 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/log2n) [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]. The 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.

Place, publisher, year, edition, pages
New York, NY, USA: ACM Digital Library, 2015. , p. 21-30p. 21-30
National Category
Computer Sciences
Research subject
Computer Science
Identifiers
URN: urn:nbn:se:kth:diva-232465DOI: 10.1145/2746539.2746609Scopus ID: 2-s2.0-84958762655ISBN: 978-1-4503-3536-2 OAI: oai:DiVA.org:kth-232465DiVA, id: diva2:1234274
Conference
STOC '15 Symposium on Theory of Computing (part of FCRC) Portland, OR, USA — June 14 - 17, 2015
Note

QC 20180724

Available from: 2018-07-24 Created: 2018-07-24 Last updated: 2018-07-25Bibliographically approved

Open Access in DiVA

fulltext(2624 kB)4 downloads
File information
File name FULLTEXT01.pdfFile size 2624 kBChecksum SHA-512
f205c273816bbd4cd7fa3a4aaa14d19e5247ef81649a04bc53175a5db6720328ff20c3050d413a871a4e0ef25c57a11aaee78aea83d0033e273ffa5f71c7b2de
Type fulltextMimetype application/pdf

Other links

Publisher's full textScopushttps://dl.acm.org/citation.cfm?id=2746609

Search in DiVA

By author/editor
Na Nongkai, DanuponSaranurak, Thatchaphol
By organisation
Theoretical Computer Science, TCS
Computer Sciences

Search outside of DiVA

GoogleGoogle Scholar
Total: 4 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

doi
isbn
urn-nbn

Altmetric score

doi
isbn
urn-nbn
Total: 0 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf