Improved Pattern-Avoidance Bounds for Greedy BSTs via Matrix Decomposition

Research output: Chapter in Book/Report/Conference proceedingConference article in proceedingsScientificpeer-review

1 Citation (Scopus)
8 Downloads (Pure)

Abstract

Greedy BST (or simply Greedy) is an online self-adjusting binary search tree defined in the geometric view ([Lucas, 1988; Munro, 2000; Demaine, Harmon, Iacono, Kane, Patrascu, SODA 2009). Along with Splay trees (Sleator, Tarjan 1985), Greedy is considered the most promising candidate for being dynamically optimal, i.e., starting with any initial tree, their access costs on any sequence is conjectured to be within O(1) factor of the offline optimal. However, despite having received a lot of attention in the past four decades, the question has remained elusive even for highly restricted input. In this paper, we prove new bounds on the cost of Greedy in the “pattern avoidance” regime. Our new results include: • The (preorder) traversal conjecture for Greedy holds up to a factor of O(2α(n)), improving upon the bound of 2α(n)O(1) in (Chalermsook et al., FOCS 2015) where α(n) is the inverse Ackermann function of n. This is the best known bound obtained by any online BSTs. • We settle the postorder traversal conjecture for Greedy. Previously this was shown for Splay trees only in certain special cases (Levy and Tarjan, WADS 2019). • The deque conjecture for Greedy holds up to a factor of O(α(n)), improving upon the bound 2O(α(n)) in (Chalermsook, et al., WADS 2015). This is arguably “one step away” from the bound O(α(n)) for Splay trees (Pettie, SODA 2010). • The split conjecture holds for Greedy up to a factor of O(2α(n)). Previously the factor of O(α(n)) was shown for Splay trees only in a special case (Lucas, 1988). The input sequences in traversal and deque conjectures are perhaps “easiest” in the pattern-avoiding input classes and yet among the most notorious special cases of the dynamic optimality conjecture. Key to all these results is to partition (based on the input structures) the execution log of Greedy into several simpler-to-analyze subsets for which classical forbidden submatrix bounds can be leveraged. We believe that this simple method will find further applications in doing amortized analysis of data structures via extremal combinatorics. Finally, we show the applicability of this technique to handle a class of increasingly complex pattern-avoiding input sequences, called k-increasing sequences. As a bonus, we discover a new class of permutation matrices whose extremal bounds are polynomially bounded. This gives a partial progress on an open question by Jacob Fox (2013).

Original languageEnglish
Title of host publicationProceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)
PublisherSociety for Industrial and Applied Mathematics (SIAM)
Pages509-534
Number of pages26
ISBN (Electronic)9781611977554
DOIs
Publication statusPublished - 2023
MoE publication typeA4 Conference publication
EventACM-SIAM Symposium on Discrete Algorithms - Florence, Italy
Duration: 22 Jan 202325 Jan 2023
Conference number: 34

Conference

ConferenceACM-SIAM Symposium on Discrete Algorithms
Abbreviated titleSODA
Country/TerritoryItaly
CityFlorence
Period22/01/202325/01/2023

Fingerprint

Dive into the research topics of 'Improved Pattern-Avoidance Bounds for Greedy BSTs via Matrix Decomposition'. Together they form a unique fingerprint.

Cite this