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
Dynamic algorithms: new worst-case and instance-optimal bounds via new connections
KTH, School of Electrical Engineering and Computer Science (EECS), Theoretical Computer Science, TCS.ORCID iD: 0000-0003-3694-740X
2018 (English)Doctoral thesis, comprehensive summary (Other academic)
Abstract [en]

This thesis studies a series of questions about dynamic algorithms which are algorithms for quickly maintaining some information of an input data undergoing a sequence of updates. The first question asks \emph{how small the update time for handling each update can be} for each dynamic problem. To obtain fast algorithms, several relaxations are often used including allowing amortized update time, allowing randomization, or even assuming an oblivious adversary. Hence, the second question asks \emph{whether these relaxations and assumptions can be removed} without sacrificing the speed. Some dynamic problems are successfully solved by fast dynamic algorithms without any relaxation. The guarantee of such algorithms, however, is for a worst-case scenario. This leads to the last question which asks for \emph{an algorithm whose cost is nearly optimal for every scenario}, namely an instance-optimal algorithm. This thesis shows new progress on all three questions.

For the first question, we give two frameworks for showing the inherent limitations of fast dynamic algorithms. First, we propose a conjecture called the Online Boolean Matrix-vector Multiplication Conjecture (OMv). Assuming this conjecture, we obtain new \emph{tight} conditional lower bounds of update time for more than ten dynamic problems even when algorithms are allowed to have large polynomial preprocessing time. Second, we establish the first analogue of ``NP-completeness'' for dynamic problems, and show that many natural problems are ``NP-hard'' in the dynamic setting. This hardness result is based on the hardness of all problems in a huge class that includes a number of natural and hard dynamic problems. All previous conditional lower bounds for dynamic problems are based on hardness of specific problems/conjectures.

For the second question, we give an algorithm for maintaining a minimum spanning forest in an $n$-node graph undergoing edge insertions and deletions using $n^{o(1)}$ worst-case update time with high probability. This significantly improves the long-standing $O(\sqrt{n})$ bound by {[}Frederickson STOC'83, Eppstein, Galil, Italiano and Nissenzweig FOCS'92{]}. Previously, a spanning forest (possibly not minimum) can be maintained in polylogarithmic update time if either amortized update is allowed or an oblivious adversary is assumed. Therefore, our work shows how to eliminate these relaxations without slowing down updates too much.

For the last question, we show two main contributions on the theory of instance-optimal dynamic algorithms. First, we use the forbidden submatrix theory from combinatorics to show that a binary search tree (BST) algorithm called \emph{Greedy} has almost optimal cost when its input \emph{avoids a pattern}. This is a significant progress towards the Traversal Conjecture {[}Sleator and Tarjan JACM'85{]} and its generalization. Second, we initialize the theory of instance optimality of heaps by showing a general transformation between BSTs and heaps and then transferring the rich analogous theory of BSTs to heaps. Via the connection, we discover a new heap, called the \emph{smooth heap}, which is very simple to implement, yet inherits most guarantees from BST literature on being instance-optimal on various kinds of inputs. The common approach behind all our results is about making new connections between dynamic algorithms and other fields including fine-grained and classical complexity theory, approximation algorithms for graph partitioning, local clustering algorithms, and forbidden submatrix theory.

Place, publisher, year, edition, pages
KTH Royal Institute of Technology, 2018. , p. 51
Series
TRITA-EECS-AVL ; 2018:51
National Category
Computer Sciences
Research subject
Computer Science
Identifiers
URN: urn:nbn:se:kth:diva-232471ISBN: 978-91-7729-865-6 (print)OAI: oai:DiVA.org:kth-232471DiVA, id: diva2:1234277
Public defence
2018-08-27, F3, Kungl Tekniska högskolan, Lindstedtsvägen 26, Stockholm, 13:00 (English)
Opponent
Supervisors
Note

QC 20180725

Available from: 2018-07-25 Created: 2018-07-24 Last updated: 2018-07-25Bibliographically approved
List of papers
1. Unifying and Strengthening Hardness for Dynamic Problems via the Online Matrix-Vector Multiplication Conjecture
Open this publication in new window or tab >>Unifying and Strengthening Hardness for Dynamic Problems via the Online Matrix-Vector Multiplication Conjecture
2015 (English)In: STOC '15 Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, ACM Press, 2015, p. 21-30Conference paper, Published paper (Refereed)
Abstract [en]

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].

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
ACM Press, 2015
National Category
Computer Sciences
Identifiers
urn:nbn:se:kth:diva-165846 (URN)10.1145/2746539.2746609 (DOI)2-s2.0-84958762655 (Scopus ID)
Conference
STOC 2015: 47th Annual Symposium on the Theory of Computing,Portland, OR, June 15 - June 17 2015
Note

QC 20150811

Available from: 2015-04-29 Created: 2015-04-29 Last updated: 2018-07-24Bibliographically approved
2. Nondeterminism and Completeness for Dynamic Algorithms
Open this publication in new window or tab >>Nondeterminism and Completeness for Dynamic Algorithms
(English)Manuscript (preprint) (Other academic)
National Category
Computer Sciences
Identifiers
urn:nbn:se:kth:diva-232470 (URN)
Note

QC 20180724

Available from: 2018-07-24 Created: 2018-07-24 Last updated: 2018-07-24Bibliographically approved
3. Dynamic Minimum Spanning Forest with Subpolynomial Worst-case Update Time
Open this publication in new window or tab >>Dynamic Minimum Spanning Forest with Subpolynomial Worst-case Update Time
2017 (English)In: 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), IEEE, 2017, p. 950-961Conference paper, Published paper (Refereed)
Abstract [en]

We present a Las Vegas algorithm for dynamically maintaining a minimum spanning forest of an nnode graph undergoing edge insertions and deletions. Our algorithm guarantees an O(n(o(1))) worst-case update time with high probability. This significantly improves the two recent Las Vegas algorithms by Wulff-Nilsen [2] with update time O(n(0.5-epsilon)) for some constant epsilon > 0 and, independently, by Nanongkai and Saranurak [3] with update time O(n(0.494)) (the latter works only for maintaining a spanning forest). Our result is obtained by identifying the common framework that both two previous algorithms rely on, and then improve and combine the ideas from both works. There are two main algorithmic components of the framework that are newly improved and critical for obtaining our result. First, we improve the update time from O(n(0.5-epsilon)) in [2] to O(n(o(1))) for decrementally removing all low-conductance cuts in an expander undergoing edge deletions. Second, by revisiting the "contraction technique" by Henzinger and King [4] and Holm et al. [5], we show a new approach for maintaining a minimum spanning forest in connected graphs with very few (at most (1 + o(1))n) edges. This significantly improves the previous approach in [2], [3] which is based on Frederickson's 2-dimensional topology tree [6] and illustrates a new application to this old technique.

Place, publisher, year, edition, pages
IEEE, 2017
Series
Annual IEEE Symposium on Foundations of Computer Science, ISSN 0272-5428
National Category
Electrical Engineering, Electronic Engineering, Information Engineering Computer Sciences
Identifiers
urn:nbn:se:kth:diva-220661 (URN)10.1109/FOCS.2017.92 (DOI)000417425300083 ()2-s2.0-85041099602 (Scopus ID)978-1-5386-3464-6 (ISBN)
Conference
58th IEEE Annual Symposium on Foundations of Computer Science (FOCS), OCT 15-17, 2017, Berkeley, CA
Note

QC 20180108

Available from: 2018-01-08 Created: 2018-01-08 Last updated: 2018-07-25Bibliographically approved
4. Smooth Heaps and a Dual View of Self-adjusting Data Structures
Open this publication in new window or tab >>Smooth Heaps and a Dual View of Self-adjusting Data Structures
2018 (English)In: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, ACM , 2018, p. 801-814Conference paper, Published paper (Refereed)
Place, publisher, year, edition, pages
ACM, 2018
Series
STOC 2018
Keywords
binary search trees, heaps, self-adjusting data structures, sorting
National Category
Computer Sciences
Identifiers
urn:nbn:se:kth:diva-232468 (URN)10.1145/3188745.3188864 (DOI)
Conference
STOC 2018
Note

QC 20180814

Available from: 2018-07-24 Created: 2018-07-24 Last updated: 2018-08-14Bibliographically approved
5. Distributed Exact Weighted All-Pairs Shortest Paths in (O)over-tilde(n(5/4)) Rounds
Open this publication in new window or tab >>Distributed Exact Weighted All-Pairs Shortest Paths in (O)over-tilde(n(5/4)) Rounds
2017 (English)In: 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), IEEE, 2017, p. 168-179Conference paper, Published paper (Refereed)
Abstract [en]

We study computing all-pairs shortest paths (APSP) on distributed networks (the CONGEST model). The goal is for every node in the (weighted) network to know the distance from every other node using communication. The problem admits (1+ o(1))-approximation (O) over tilde (n)-time algorithms [2], [3], which are matched with (Omega) over tilde (n)-time lower bounds [3], [4], [5](1). No omega(n) lower bound or o(m) upper bound were known for exact computation. In this paper, we present an (O) over tilde (n(5/4))-time randomized (Las Vegas) algorithm for exact weighted APSP; this provides the first improvement over the naive O(m)-time algorithm when the network is not so sparse. Our result also holds for the case where edge weights are asymmetric (a. k. a. the directed case where communication is bidirectional). Our techniques also yield an (O) over tilde (n(3/4) k(1/2) + n)-time algorithm for the k-source shortest paths problem where we want every node to know distances from k sources; this improves Elkin's recent bound [6] when k = (omega) over tilde (n(1/4)). We achieve the above results by developing distributed algorithms on top of the classic scaling technique, which we believe is used for the first time for distributed shortest paths computation. One new algorithm which might be of an independent interest is for the reversed r-sink shortest paths problem, where we want every of r sinks to know its distances from all other nodes, given that every node already knows its distance to every sink. We show an (O) over tilde (n root r)-time algorithm for this problem. Another new algorithm is called short range extension, where we show that in (O) over tilde (n root h) time the knowledge about distances can be "extended" for additional h hops. For this, we use weight rounding to introduce small additive errors which can be later fixed. Remark: Independently from our result, Elkin recently observed in [6] that the same techniques from an earlier version of the same paper (https://arxiv.org/abs/1703.01939v1) led to an O(n(5/3) log(2/3) n)-time algorithm.

Place, publisher, year, edition, pages
IEEE, 2017
Series
Annual IEEE Symposium on Foundations of Computer Science, ISSN 0272-5428
Keywords
distributed graph algorithms, all-pairs shortest paths, exact distributed algorithms
National Category
Electrical Engineering, Electronic Engineering, Information Engineering
Identifiers
urn:nbn:se:kth:diva-220659 (URN)10.1109/FOCS.2017.24 (DOI)000417425300015 ()2-s2.0-85041116469 (Scopus ID)978-1-5386-3464-6 (ISBN)
Conference
58th IEEE Annual Symposium on Foundations of Computer Science (FOCS), OCT 15-17, 2017, Berkeley, CA
Funder
EU, Horizon 2020, 715672Swedish Research Council, 2015-04659
Note

QC 20170109

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

Open Access in DiVA

fulltext(1137 kB)32 downloads
File information
File name FULLTEXT02.pdfFile size 1137 kBChecksum SHA-512
d13e762cbed8205fb8af9f164af7d4890a0eb60a2f2f863833cb020efc886bf871ce4842bf71bd065efb3dfa3295f56ef3b99e1bd3aec59bdd61bc54b033611b
Type fulltextMimetype application/pdf

Search in DiVA

By author/editor
Saranurak, Thatchaphol
By organisation
Theoretical Computer Science, TCS
Computer Sciences

Search outside of DiVA

GoogleGoogle Scholar
Total: 32 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

isbn
urn-nbn

Altmetric score

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