Please wait ... |

Link to record
http://kth.diva-portal.org/smash/person.jsf?pid=authority-person:32570 $(function(){PrimeFaces.cw("InputTextarea","widget_formSmash_upper_j_idt122_recordDirectLink",{id:"formSmash:upper:j_idt122:recordDirectLink",widgetVar:"widget_formSmash_upper_j_idt122_recordDirectLink",autoResize:true});}); $(function(){PrimeFaces.cw("OverlayPanel","widget_formSmash_upper_j_idt122_j_idt124",{id:"formSmash:upper:j_idt122:j_idt124",widgetVar:"widget_formSmash_upper_j_idt122_j_idt124",target:"formSmash:upper:j_idt122:permLink",showEffect:"blind",hideEffect:"fade",my:"right top",at:"right bottom",showCloseIcon:true});});

Permanent link

Direct link

Saranurak, Thatchapholorcid.org/0000-0003-3694-740X

Open this publication in new window or tab >>Dynamic algorithms: new worst-case and instance-optimal bounds via new connections### Saranurak, Thatchaphol

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_0_j_idt188_some",{id:"formSmash:j_idt184:0:j_idt188:some",widgetVar:"widget_formSmash_j_idt184_0_j_idt188_some",multiple:true}); PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_0_j_idt188_otherAuthors",{id:"formSmash:j_idt184:0:j_idt188:otherAuthors",widgetVar:"widget_formSmash_j_idt184_0_j_idt188_otherAuthors",multiple:true}); 2018 (English)Doctoral thesis, comprehensive summary (Other academic)
##### Abstract [en]

##### 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:nbn:se:kth:diva-232471 (URN)978-91-7729-865-6 (ISBN)
##### Public defence

2018-08-27, F3, Kungl Tekniska högskolan, Lindstedtsvägen 26, Stockholm, 13:00 (English)
##### Opponent

### Sankowski, Piotr

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_0_j_idt188_j_idt359",{id:"formSmash:j_idt184:0:j_idt188:j_idt359",widgetVar:"widget_formSmash_j_idt184_0_j_idt188_j_idt359",multiple:true});
##### Supervisors

### Nanongkai, Danupon

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_0_j_idt188_j_idt365",{id:"formSmash:j_idt184:0:j_idt188:j_idt365",widgetVar:"widget_formSmash_j_idt184_0_j_idt188_j_idt365",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_0_j_idt188_j_idt371",{id:"formSmash:j_idt184:0:j_idt188:j_idt371",widgetVar:"widget_formSmash_j_idt184_0_j_idt188_j_idt371",multiple:true});
#####

##### Note

KTH, School of Electrical Engineering and Computer Science (EECS), Theoretical Computer Science, TCS.

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.

Warsaw University, Institute of Informatics, Warsaw, Poland.

KTH, School of Electrical Engineering and Computer Science (EECS), Theoretical Computer Science, TCS.

QC 20180725

Available from: 2018-07-25 Created: 2018-07-24 Last updated: 2018-07-25Bibliographically approvedOpen this publication in new window or tab >>Smooth Heaps and a Dual View of Self-adjusting Data Structures### Kozma, László

### Saranurak, Thatchaphol

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_1_j_idt188_some",{id:"formSmash:j_idt184:1:j_idt188:some",widgetVar:"widget_formSmash_j_idt184_1_j_idt188_some",multiple:true}); PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_1_j_idt188_otherAuthors",{id:"formSmash:j_idt184:1:j_idt188:otherAuthors",widgetVar:"widget_formSmash_j_idt184_1_j_idt188_otherAuthors",multiple:true}); 2018 (English)In: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, ACM , 2018, p. 801-814Conference paper, Published paper (Refereed)
##### Abstract [en]

##### 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)000458175600069 ()2-s2.0-85049889551 (Scopus ID)
##### Conference

50th Annual ACM Symposium on Theory of Computing, STOC 2018; Los Angeles; United States; 25 June 2018 through 29 June 2018
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_1_j_idt188_j_idt359",{id:"formSmash:j_idt184:1:j_idt188:j_idt359",widgetVar:"widget_formSmash_j_idt184_1_j_idt188_j_idt359",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_1_j_idt188_j_idt365",{id:"formSmash:j_idt184:1:j_idt188:j_idt365",widgetVar:"widget_formSmash_j_idt184_1_j_idt188_j_idt365",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_1_j_idt188_j_idt371",{id:"formSmash:j_idt184:1:j_idt188:j_idt371",widgetVar:"widget_formSmash_j_idt184_1_j_idt188_j_idt371",multiple:true});
#####

##### Note

KTH, School of Electrical Engineering and Computer Science (EECS), Theoretical Computer Science, TCS.

We present a new connection between self-adjusting binary search trees (BSTs) and heaps, two fundamental, extensively studied, and practically relevant families of data structures (Allen, Munro, 1978; Sleator, Tarjan, 1983; Fredman, Sedgewick, Sleator, Tarjan, 1986; Wilber, 1989; Fredman, 1999; Iacono, Özkan, 2014). Roughly speaking, we map an arbitrary heap algorithm within a broad and natural model, to a corresponding BST algorithm with the same cost on a dual sequence of operations (i.e. the same sequence with the roles of time and key-space switched). This is the first general transformation between the two families of data structures. There is a rich theory of dynamic optimality for BSTs (i.e. the theory of competitiveness between BST algorithms). The lack of an analogous theory for heaps has been noted in the literature (e.g. Pettie; 2005, 2008). Through our connection, we transfer all instance-specific lower bounds known for BSTs to a general model of heaps, initiating a theory of dynamic optimality for heaps. On the algorithmic side, we obtain a new, simple and efficient heap algorithm, which we call the smooth heap. We show the smooth heap to be the heap-counterpart of Greedy, the BST algorithm with the strongest proven and conjectured properties from the literature, widely believed to be instance-optimal (Lucas, 1988; Munro, 2000; Demaine et al., 2009). Assuming the optimality of Greedy, the smooth heap is also optimal within our model of heap algorithms. Intriguingly, the smooth heap, although derived from a non-practical BST algorithm, is simple and easy to implement (e.g. it stores no auxiliary data besides the keys and tree pointers). It can be seen as a variation on the popular pairing heap data structure, extending it with a “power-of-two-choices” type of heuristic. For the smooth heap we obtain instance-specific upper bounds, with applications in adaptive sorting, and we see it as a promising candidate for the long-standing question of a simpler alternative to Fibonacci heaps. The paper is dedicated to Raimund Seidel on occasion of his sixtieth birthday.

QC 20180814

Available from: 2018-07-24 Created: 2018-07-24 Last updated: 2019-02-22Bibliographically approvedOpen this publication in new window or tab >>Distributed Exact Weighted All-Pairs Shortest Paths in (O)over-tilde(n(5/4)) Rounds### Huang, Chien-Chung

### Na Nongkai, Danupon

### Saranurak, Thatchaphol

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_2_j_idt188_some",{id:"formSmash:j_idt184:2:j_idt188:some",widgetVar:"widget_formSmash_j_idt184_2_j_idt188_some",multiple:true}); PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_2_j_idt188_otherAuthors",{id:"formSmash:j_idt184:2:j_idt188:otherAuthors",widgetVar:"widget_formSmash_j_idt184_2_j_idt188_otherAuthors",multiple:true}); 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]

##### 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
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_2_j_idt188_j_idt359",{id:"formSmash:j_idt184:2:j_idt188:j_idt359",widgetVar:"widget_formSmash_j_idt184_2_j_idt188_j_idt359",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_2_j_idt188_j_idt365",{id:"formSmash:j_idt184:2:j_idt188:j_idt365",widgetVar:"widget_formSmash_j_idt184_2_j_idt188_j_idt365",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_2_j_idt188_j_idt371",{id:"formSmash:j_idt184:2:j_idt188:j_idt371",widgetVar:"widget_formSmash_j_idt184_2_j_idt188_j_idt371",multiple:true});
#####

##### Funder

EU, Horizon 2020, 715672Swedish Research Council, 2015-04659
##### Note

KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.

KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.

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.

QC 20170109

Available from: 2018-01-09 Created: 2018-01-09 Last updated: 2018-07-24Bibliographically approvedOpen this publication in new window or tab >>Dynamic Minimum Spanning Forest with Subpolynomial Worst-case Update Time### Na Nongkai, Danupon

### Saranurak, Thatchaphol

### Wulff-Nilsen, Christian

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_3_j_idt188_some",{id:"formSmash:j_idt184:3:j_idt188:some",widgetVar:"widget_formSmash_j_idt184_3_j_idt188_some",multiple:true}); PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_3_j_idt188_otherAuthors",{id:"formSmash:j_idt184:3:j_idt188:otherAuthors",widgetVar:"widget_formSmash_j_idt184_3_j_idt188_otherAuthors",multiple:true}); 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]

##### 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
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_3_j_idt188_j_idt359",{id:"formSmash:j_idt184:3:j_idt188:j_idt359",widgetVar:"widget_formSmash_j_idt184_3_j_idt188_j_idt359",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_3_j_idt188_j_idt365",{id:"formSmash:j_idt184:3:j_idt188:j_idt365",widgetVar:"widget_formSmash_j_idt184_3_j_idt188_j_idt365",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_3_j_idt188_j_idt371",{id:"formSmash:j_idt184:3:j_idt188:j_idt371",widgetVar:"widget_formSmash_j_idt184_3_j_idt188_j_idt371",multiple:true});
#####

##### Note

KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.

KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.

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.

QC 20180108

Available from: 2018-01-08 Created: 2018-01-08 Last updated: 2018-07-25Bibliographically approvedOpen this publication in new window or tab >>Greedy is an almost optimal deque### Chalermsook, P.

### Goswami, M.

### Kozma, L.

### Mehlhorn, K.

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_4_j_idt188_some",{id:"formSmash:j_idt184:4:j_idt188:some",widgetVar:"widget_formSmash_j_idt184_4_j_idt188_some",multiple:true}); ### Saranurak, Thatchaphol

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_4_j_idt188_otherAuthors",{id:"formSmash:j_idt184:4:j_idt188:otherAuthors",widgetVar:"widget_formSmash_j_idt184_4_j_idt188_otherAuthors",multiple:true}); Show others...PrimeFaces.cw("SelectBooleanButton","widget_formSmash_j_idt184_4_j_idt188_j_idt202",{id:"formSmash:j_idt184:4:j_idt188:j_idt202",widgetVar:"widget_formSmash_j_idt184_4_j_idt188_j_idt202",onLabel:"Hide others...",offLabel:"Show others..."}); 2015 (English)In: 14th International Symposium on Algorithms and Data Structures, WADS 2015, Springer, 2015, p. 152-165Conference paper, Published paper (Refereed)
##### Abstract [en]

##### Place, publisher, year, edition, pages

Springer, 2015
##### Series

Lecture Notes in Computer Science, ISSN 0302-9743 ; 9214
##### Keywords

Algorithms, Data structures, Forestry, Access cost, Binary search trees, Dynamic optimality, Extended model, High probability, Insertions and deletions, Quasi-linear, Random permutations, Binary trees
##### National Category

Control Engineering
##### Identifiers

urn:nbn:se:kth:diva-181504 (URN)10.1007/978-3-319-21840-3_13 (DOI)2-s2.0-84951865390 (Scopus ID)9783319218397 (ISBN)
##### Conference

5 August 2015 through 7 August 2015
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_4_j_idt188_j_idt359",{id:"formSmash:j_idt184:4:j_idt188:j_idt359",widgetVar:"widget_formSmash_j_idt184_4_j_idt188_j_idt359",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_4_j_idt188_j_idt365",{id:"formSmash:j_idt184:4:j_idt188:j_idt365",widgetVar:"widget_formSmash_j_idt184_4_j_idt188_j_idt365",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_4_j_idt188_j_idt371",{id:"formSmash:j_idt184:4:j_idt188:j_idt371",widgetVar:"widget_formSmash_j_idt184_4_j_idt188_j_idt371",multiple:true});
#####

##### Note

KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.

In this paper we extend the geometric binary search tree (BST) model of Demaine, Harmon, Iacono, Kane, and Pătraşcu (DHIKP) to accommodate for insertions and deletions. Within this extended model, we study the online GREEDY BST algorithm introduced by DHIKP. GREEDY BST is known to be equivalent to a maximally greedy (but inherently offline) algorithm introduced independently by Lucas in 1988 and Munro in 2000, conjectured to be dynamically optimal. With the application of forbidden-submatrix theory, we prove a quasilinear upper bound on the performance of GREEDY BST on deque sequences. It has been conjectured (Tarjan, 1985) that splay trees (Sleator and Tarjan, 1983) can serve such sequences in linear time. Currently neither splay trees, nor other general-purpose BST algorithms are known to fulfill this requirement. As a special case, we show that GREEDY BST can serve output-restricted deque sequences in linear time. A similar result is known for splay trees (Tarjan, 1985; Elmasry, 2004). As a further application of the insert-delete model, we give a simple proof that, given a set U of permutations of [n], the access cost of any BST algorithm is Ω(log |U| + n) on “most” of the permutations from U. In particular, this implies that the access cost for a random permutation of [n] is Ω(n log n) with high probability. Besides the splay tree noted before, GREEDY BST has recently emerged as a plausible candidate for dynamic optimality. Compared to splay trees, much less effort has gone into analyzing GREEDY BST. Our work is intended as a step towards a full understanding of GREEDY BST, and we remark that forbidden-submatrix arguments seem particularly well suited for carrying out this program.

QC 20160204

Available from: 2016-02-04 Created: 2016-02-02 Last updated: 2016-02-04Bibliographically approvedOpen this publication in new window or tab >>Pattern-Avoiding Access in Binary Search Trees### Chalermsook, P.

### Goswami, M.

### Kozma, L.

### Mehlhorn, K.

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_5_j_idt188_some",{id:"formSmash:j_idt184:5:j_idt188:some",widgetVar:"widget_formSmash_j_idt184_5_j_idt188_some",multiple:true}); ### Saranurak, Thatchaphol

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_5_j_idt188_otherAuthors",{id:"formSmash:j_idt184:5:j_idt188:otherAuthors",widgetVar:"widget_formSmash_j_idt184_5_j_idt188_otherAuthors",multiple:true}); Show others...PrimeFaces.cw("SelectBooleanButton","widget_formSmash_j_idt184_5_j_idt188_j_idt202",{id:"formSmash:j_idt184:5:j_idt188:j_idt202",widgetVar:"widget_formSmash_j_idt184_5_j_idt188_j_idt202",onLabel:"Hide others...",offLabel:"Show others..."}); 2015 (English)In: Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS, Institute of Electrical and Electronics Engineers (IEEE), 2015, p. 410-423Conference paper, Published paper (Refereed)
##### Abstract [en]

##### Place, publisher, year, edition, pages

Institute of Electrical and Electronics Engineers (IEEE), 2015
##### Keywords

binary search trees, pattern-avoidance
##### National Category

Electrical Engineering, Electronic Engineering, Information Engineering
##### Identifiers

urn:nbn:se:kth:diva-186801 (URN)10.1109/FOCS.2015.32 (DOI)000379204700023 ()2-s2.0-84960468390 (Scopus ID)9781467381918 (ISBN)
##### Conference

56th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2015, 17 October 2015 through 20 October 2015
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_5_j_idt188_j_idt359",{id:"formSmash:j_idt184:5:j_idt188:j_idt359",widgetVar:"widget_formSmash_j_idt184_5_j_idt188_j_idt359",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_5_j_idt188_j_idt365",{id:"formSmash:j_idt184:5:j_idt188:j_idt365",widgetVar:"widget_formSmash_j_idt184_5_j_idt188_j_idt365",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_5_j_idt188_j_idt371",{id:"formSmash:j_idt184:5:j_idt188:j_idt371",widgetVar:"widget_formSmash_j_idt184_5_j_idt188_j_idt371",multiple:true});
#####

##### Note

KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.

The dynamic optimality conjecture is perhaps the most fundamental open question about binary search trees (BST). It postulates the existence of an asymptotically optimal online BST, i.e. One that is constant factor competitive with any BST on any input access sequence. The two main candidates for dynamic optimality in the literature are splay trees [Sleator and Tarjan, 1985], and Greedy [Lucas, 1988, Munro, 2000, Demaine et al. 2009]. Despite BSTs being among the simplest data structures in computer science, and despite extensive effort over the past three decades, the conjecture remains elusive. Dynamic optimality is trivial for almost all sequences: the optimum access cost of most length-n sequences is Theta(n log n), achievable by any balanced BST. Thus, the obvious missing step towards the conjecture is an understanding of the 'easy' access sequences, and indeed the most fruitful research direction so far has been the study of specific sequences, whose 'easiness' is captured by a parameter of interest. For instance, splay provably achieves the bound of O(nd) when d roughly measures the distances between consecutive accesses (dynamic finger), the average entropy (static optimality), or the delays between multiple accesses of an element(working set). The difficulty of proving dynamic optimality is witnessed by other highly restricted special cases that remain unresolved, one prominent example is the traversal conjecture [Sleator and Tarjan, 1985], which states that preorder sequences (whose optimum is linear) are linear-time accessed by splay trees, no online BST is known to satisfy this conjecture. In this paper, we prove two different relaxations of the traversal conjecture for Greedy: (i) Greedy is almost linear for preorder traversal, (ii) if a linear-time preprocessing is allowed, Greedy is in fact linear. These statements are corollaries of our more general results that express the complexity of access sequences in terms of a pattern avoidance parameter k. Pattern avoidance is a well-established concept in combinatorics, and the classes of input sequences thus defined are rich, e.g. The k = 3 case includes preorder sequences. For any sequence X with parameter k, our most general result shows that Greedy achieves the cost n2α(n)O(k) where α is the inverse Ackermann function. Furthermore, a broad subclass of parameter-k sequences has a natural combinatorial interpretation as k-decomposable sequences. For this class of inputs, we obtain an n∗2O(k) bound for Greedy when preprocessing is allowed. For k = 3, these results imply (i) and (ii). To our knowledge, these are the first upper bounds for Greedy that are not known to hold for any other online BST. To obtain these results we identify an input-revealing property of Greedy. Informally, this means that the execution log partially reveals the structure of the access sequence. This property facilitates the use of rich technical tools from forbidden sub matrix theory. Further studying the intrinsic complexity of k-decomposable sequences, we make several observations. First, in order to obtain an offline optimal BST, it is enough to bound Greedy on non-decomposable access sequences. Furthermore, we show that the optimal cost for k-decomposable sequences is Theta(n log k), which is well below the proven performance of all known BST algorithms. Hence, sequences in this class can be seen as a 'candidate counterexample' to dynamic optimality. © 2015 IEEE.

QC 20160516

Available from: 2016-05-16 Created: 2016-05-13 Last updated: 2018-12-05Bibliographically approvedOpen this publication in new window or tab >>Self-Adjusting Binary Search Trees: What Makes Them Tick?### Chalermsook, Parinya

### Goswami, Mayank

### Kozma, Laszlo

### Mehlhorn, Kurt

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_6_j_idt188_some",{id:"formSmash:j_idt184:6:j_idt188:some",widgetVar:"widget_formSmash_j_idt184_6_j_idt188_some",multiple:true}); ### Saranurak, Thatchaphol

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_6_j_idt188_otherAuthors",{id:"formSmash:j_idt184:6:j_idt188:otherAuthors",widgetVar:"widget_formSmash_j_idt184_6_j_idt188_otherAuthors",multiple:true}); Show others...PrimeFaces.cw("SelectBooleanButton","widget_formSmash_j_idt184_6_j_idt188_j_idt202",{id:"formSmash:j_idt184:6:j_idt188:j_idt202",widgetVar:"widget_formSmash_j_idt184_6_j_idt188_j_idt202",onLabel:"Hide others...",offLabel:"Show others..."}); 2015 (English)In: ALGORITHMS - ESA 2015, Springer Verlag , 2015, p. 300-312Conference paper, Published paper (Refereed)
##### Abstract [en]

##### Place, publisher, year, edition, pages

Springer Verlag, 2015
##### Series

Lecture Notes in Computer Science, ISSN 0302-9743 ; 9294
##### National Category

Computer Sciences
##### Identifiers

urn:nbn:se:kth:diva-180171 (URN)10.1007/978-3-662-48350-3_26 (DOI)000366210300028 ()2-s2.0-84945581492 (Scopus ID)978-3-662-48350-3; 978-3-662-48349-7 (ISBN)
##### Conference

23rd Annual European Symposium on Algorithms (ESA) as part of ALGO Conference, SEP 14-16, 2015, Patras, GREECE
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_6_j_idt188_j_idt359",{id:"formSmash:j_idt184:6:j_idt188:j_idt359",widgetVar:"widget_formSmash_j_idt184_6_j_idt188_j_idt359",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_6_j_idt188_j_idt365",{id:"formSmash:j_idt184:6:j_idt188:j_idt365",widgetVar:"widget_formSmash_j_idt184_6_j_idt188_j_idt365",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_6_j_idt188_j_idt371",{id:"formSmash:j_idt184:6:j_idt188:j_idt371",widgetVar:"widget_formSmash_j_idt184_6_j_idt188_j_idt371",multiple:true});
#####

##### Note

KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS. Saarland University, Germany.

Splay trees (Sleator and Tarjan [11]) satisfy the so-called access lemma. Many of the nice properties of splay trees follow from it. What makes self-adjusting binary search trees (BSTs) satisfy the access lemma? After each access, self-adjusting BSTs replace the search path by a tree on the same set of nodes (the after-tree). We identify two simple combinatorial properties of the search path and the after-tree that imply the access lemma. Our main result (i) implies the access lemma for all minimally self-adjusting BST algorithms for which it was known to hold: splay trees and their generalization to the class of local algorithms (Subramanian [12], Georgakopoulos and McClurkin [7]), as well as Greedy BST, introduced by Demaine et al. [5] and shown to satisfy the access lemma by Fox [6], (ii) implies that BST algorithms based on "strict" depth-halving satisfy the access lemma, addressing an open question that was raised several times since 1985, and (iii) yields an extremely short proof for the O(log n log log n) amortized access cost for the path-balance heuristic (proposed by Sleator), matching the best known bound (Balasubramanian and Raman [2]) to a lower-order factor. One of our combinatorial properties is locality. We show that any BST-algorithm that satisfies the access lemma via the sum-of-log (SOL) potential is necessarily local. The other property states that the sum of the number of leaves of the after-tree plus the number of side alternations in the search path must be at least a constant fraction of the length of the search path. We show that a weak form of this property is necessary for sequential access to be linear.

QC 20160112

Available from: 2016-01-12 Created: 2016-01-07 Last updated: 2018-01-10Bibliographically approvedOpen this publication in new window or tab >>Unifying and Strengthening Hardness for Dynamic Problems via the Online Matrix-Vector Multiplication Conjecture### Henzinger, Monika

### Krinninger, Sebastian

### Na Nongkai, Danupon

### Saranurak, Thatchaphol

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_7_j_idt188_some",{id:"formSmash:j_idt184:7:j_idt188:some",widgetVar:"widget_formSmash_j_idt184_7_j_idt188_some",multiple:true}); PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_7_j_idt188_otherAuthors",{id:"formSmash:j_idt184:7:j_idt188:otherAuthors",widgetVar:"widget_formSmash_j_idt184_7_j_idt188_otherAuthors",multiple:true}); 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]

##### 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
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_7_j_idt188_j_idt359",{id:"formSmash:j_idt184:7:j_idt188:j_idt359",widgetVar:"widget_formSmash_j_idt184_7_j_idt188_j_idt359",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_7_j_idt188_j_idt365",{id:"formSmash:j_idt184:7:j_idt188:j_idt365",widgetVar:"widget_formSmash_j_idt184_7_j_idt188_j_idt365",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_7_j_idt188_j_idt371",{id:"formSmash:j_idt184:7:j_idt188:j_idt371",widgetVar:"widget_formSmash_j_idt184_7_j_idt188_j_idt371",multiple:true});
#####

##### Note

University of Vienna.

University of Vienna.

KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.

KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.

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 v_{1}, ..., v_{n}, one by one. After seeing each vector v_{i}, we have to output the product Mv_{i} before we can see the next vector. A naive algorithm can solve this problem using O(n^{3}) time in total, and its running time can be slightly improved to O(n^{3}/log^{2} n) [Williams SODA'07]. We show that a conjecture that there is no *truly subcubic* (O(n^{3-ε})) 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.

QC 20150811

Available from: 2015-04-29 Created: 2015-04-29 Last updated: 2018-07-24Bibliographically approvedOpen this publication in new window or tab >>Nondeterminism and Completeness for Dynamic Algorithms### Bhattacharya, Sayan

### Na Nongkai, Danupon

KTH, School of Electrical Engineering and Computer Science (EECS), Theoretical Computer Science, TCS.### Saranurak, Thatchaphol

KTH, School of Electrical Engineering and Computer Science (EECS), Theoretical Computer Science, TCS.PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_8_j_idt188_some",{id:"formSmash:j_idt184:8:j_idt188:some",widgetVar:"widget_formSmash_j_idt184_8_j_idt188_some",multiple:true}); PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_8_j_idt188_otherAuthors",{id:"formSmash:j_idt184:8:j_idt188:otherAuthors",widgetVar:"widget_formSmash_j_idt184_8_j_idt188_otherAuthors",multiple:true}); (English)Manuscript (preprint) (Other academic)
##### National Category

Computer Sciences
##### Identifiers

urn:nbn:se:kth:diva-232470 (URN)
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_8_j_idt188_j_idt359",{id:"formSmash:j_idt184:8:j_idt188:j_idt359",widgetVar:"widget_formSmash_j_idt184_8_j_idt188_j_idt359",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_8_j_idt188_j_idt365",{id:"formSmash:j_idt184:8:j_idt188:j_idt365",widgetVar:"widget_formSmash_j_idt184_8_j_idt188_j_idt365",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_8_j_idt188_j_idt371",{id:"formSmash:j_idt184:8:j_idt188:j_idt371",widgetVar:"widget_formSmash_j_idt184_8_j_idt188_j_idt371",multiple:true});
#####

##### Note

University of Warwick, UK.

QC 20180724

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