Projects per year
Abstract
Greedy BST (or simply Greedy) is an online selfadjusting 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 2^{O(α(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 patternavoiding 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 simplertoanalyze 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 patternavoiding input sequences, called kincreasing 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 language  English 

Title of host publication  Proceedings of the 2023 Annual ACMSIAM Symposium on Discrete Algorithms (SODA) 
Publisher  Society for Industrial and Applied Mathematics (SIAM) 
Pages  509534 
Number of pages  26 
ISBN (Electronic)  9781611977554 
DOIs  
Publication status  Published  2023 
MoE publication type  A4 Conference publication 
Event  ACMSIAM Symposium on Discrete Algorithms  Florence, Italy Duration: 22 Jan 2023 → 25 Jan 2023 Conference number: 34 
Conference
Conference  ACMSIAM Symposium on Discrete Algorithms 

Abbreviated title  SODA 
Country/Territory  Italy 
City  Florence 
Period  22/01/2023 → 25/01/2023 
Fingerprint
Dive into the research topics of 'Improved PatternAvoidance Bounds for Greedy BSTs via Matrix Decomposition'. Together they form a unique fingerprint.Projects
 1 Finished

ALGOCom: Novel Algorithmic Techniques through the Lens of Combinatorics
Chalermsook, P., Jindal, G., Franck, M., Jiamjitrak, W., Khodamoradi, K., Yingchareonthawornchai, S., Gadekar, A., Orgo, L. & Spoerhase, J.
01/02/2018 → 31/01/2024
Project: EU: ERC grants