Hardness Amplification for Dynamic Binary Search Trees

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Jiang, Shunhua, Lecomte, Victor, Weinstein, Omri, Yingchareonthawornchai, Sorrachai
Format:	Preprint
Published:	2024
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Approximating the Held-Karp Bound for Metric TSP in Nearly Linear Work and Polylogarithmic Depth
by: Koh, Zhuan Khye, et al.
Published: (2024)

A Framework for Building Data Structures from Communication Protocols
by: Andoni, Alexandr, et al.
Published: (2025)

Directed and Undirected Vertex Connectivity Problems are Equivalent for Dense Graphs
by: Fischer, Olivier, et al.
Published: (2025)

Global vs. s-t Vertex Connectivity Beyond Sequential: Almost-Perfect Reductions & Near-Optimal Separations
by: Blikstad, Joakim, et al.
Published: (2025)

Deterministic Vertex Connectivity via Common-Neighborhood Clustering and Pseudorandomness
by: Jiang, Yonggang, et al.
Published: (2025)

A Little Clairvoyance Is All You Need
by: Gupta, Anupam, et al.
Published: (2025)

A Simpler Analysis for $\varepsilon$-Clairvoyant Flow Time Scheduling
by: Gupta, Anupam, et al.
Published: (2026)

Improved Sparse Recovery for Approximate Matrix Multiplication
by: Uffenheimer, Yahel, et al.
Published: (2026)

(Approximate) Matrix Multiplication via Convolutions
by: Uffenheimer, Yahel, et al.
Published: (2025)

A Dynamic Low-Rank Fast Gaussian Transform
by: Huang, Baihe, et al.
Published: (2022)

Discrepancy Minimization in Input-Sparsity Time
by: Deng, Yichuan, et al.
Published: (2022)

Dynamic Kernel Graph Sparsifiers
by: Cao, Yang, et al.
Published: (2022)

Generalized Flow in Nearly-linear Time on Moderately Dense Graphs
by: Jiang, Shunhua, et al.
Published: (2025)

Acceleration Meets Inverse Maintenance: Faster $\ell_{\infty}$-Regression
by: Adil, Deeksha, et al.
Published: (2024)

Hardness of Dynamic Tree Edit Distance and Friends
by: Hu, Bingbing, et al.
Published: (2025)

Automating the Search for Small Hard Examples to Approximation Algorithms
by: Sharma, Eklavya
Published: (2025)

Noisy (Binary) Searching: Simple, Fast and Correct
by: Dereniowski, Dariusz, et al.
Published: (2021)

Sparse Navigable Graphs for Nearest Neighbor Search: Algorithms and Hardness
by: Khanna, Sanjeev, et al.
Published: (2025)

Hardness of sampling solutions from the Symmetric Binary Perceptron
by: Alaoui, Ahmed El, et al.
Published: (2024)

Training Overparametrized Neural Networks in Sublinear Time
by: Deng, Yichuan, et al.
Published: (2022)

HART: A Hybrid Addressing Scheme for Self-Balancing Binary Search Trees in Phase Change Memory (PCM)
by: Desai, Mahek, et al.
Published: (2025)

Global Predecessor Indexing: Avoiding Binary Search in Weighted Job Scheduling
by: Joshi, Amit
Published: (2025)

Designing Approximate Binary Trees for Trees
by: Kellerhals, Leon, et al.
Published: (2026)

Changing Base Without Losing Pace: A GPU-Efficient Alternative to MatMul in DNNs
by: Ailon, Nir, et al.
Published: (2025)

Bounds and Algorithms for Alphabetic Codes and Binary Search Trees
by: Bruno, Roberto, et al.
Published: (2024)

In the Search of Optimal Tree Networks: Hardness and Heuristics
by: Buzdalov, Maxim, et al.
Published: (2024)

Implementing Binary Search Trees in GP 2 (Extended Abstract)
by: Alaoui, Ziad Ismaili, et al.
Published: (2026)

Approximate counting of permutation patterns
by: Ben-Eliezer, Omri, et al.
Published: (2024)

Robust Streaming Against Low-Memory Adversaries
by: Ben-Eliezer, Omri, et al.
Published: (2025)

Binary Search with Distributional Predictions
by: Dinitz, Michael, et al.
Published: (2024)

Dynamic Breadth First Search with Predictions
by: Khan, Shahbaz, et al.
Published: (2026)

Tree Search With Predictions
by: Dinitz, Michael, et al.
Published: (2026)

Search Trees on Trees via LP
by: Sadeh, Yaniv, et al.
Published: (2025)

Destroying Densest Subgraphs is Hard
by: Bazgan, Cristina, et al.
Published: (2024)

Hardness and Approximation for Coloring Digraphs
by: Chalermsook, Parinya, et al.
Published: (2026)

Hardness of Dynamic Core and Truss Decompositions
by: Couto, Yan S., et al.
Published: (2025)

Hitting Meets Packing: How Hard Can it Be?
by: Focke, Jacob, et al.
Published: (2024)

Approximations and Hardness of Packing Partially Ordered Items
by: Doron-Arad, Ilan, et al.
Published: (2024)

Hardness and Tight Approximations of Demand Strip Packing
by: Jansen, Klaus, et al.
Published: (2024)

Hardness and Approximation Algorithms for Balanced Districting Problems
by: Dharangutte, Prathamesh, et al.
Published: (2025)