Cover Image

Adaptive BSTs for Single-Source and All-to-All Requests: Algorithms and Lower Bounds

Fuente: arXiv

Saved in:

Bibliographic Details
Main Author:	Shiran, Maryam
Format:	Preprint
Published:	2025
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Lower Bounds for Adaptive Relaxation-Based Algorithms for Single-Source Shortest Paths
by: Atalig, Sunny, et al.
Published: (2024)

(Almost) Ruling Out SETH Lower Bounds for All-Pairs Max-Flow
by: Trabelsi, Ohad
Published: (2023)

New Algorithms and Lower Bounds for Streaming Tournaments
by: Ghosh, Prantar, et al.
Published: (2024)

Dynamic PageRank: Algorithms and Lower Bounds
by: Jayaram, Rajesh, et al.
Published: (2024)

One Attack to Rule Them All: Tight Quadratic Bounds for Adaptive Queries on Cardinality Sketches
by: Cohen, Edith, et al.
Published: (2024)

Bounded Weighted Edit Distance: Dynamic Algorithms and Matching Lower Bounds
by: Boneh, Itai, et al.
Published: (2025)

Lower Bounds for Non-adaptive Local Computation Algorithms
by: Azarmehr, Amir, et al.
Published: (2025)

Pareto Sums of Pareto Sets: Lower Bounds and Algorithms
by: Funke, Daniel, et al.
Published: (2024)

Tight Static Lower Bounds for Non-Adaptive Data Structures
by: Persiano, Giuseppe, et al.
Published: (2020)

Oblivious Algorithms for Maximum Directed Cut: New Upper and Lower Bounds
by: Hwang, Samuel, et al.
Published: (2024)

A Lower Bound for the Max Entropy Algorithm for TSP
by: Jin, Billy, et al.
Published: (2023)

Sensitivity Lower Bounds for Approximaiton Algorithms
by: Fleming, Noah, et al.
Published: (2024)

Convex Optimization with Local Label Differential Privacy: Tight Bounds in All Privacy Regimes
by: Chua, Lynn, et al.
Published: (2026)

Sublinear-Time Lower Bounds for Approximating Matching Size using Non-Adaptive Queries
by: Shah, Vihan
Published: (2026)

Tight (S)ETH-based Lower Bounds for Pseudopolynomial Algorithms for Bin Packing and Multi-Machine Scheduling
by: Bringmann, Karl, et al.
Published: (2026)

Lower Bounds for the Algorithmic Complexity of Learned Indexes
by: Croquevielle, Luis Alberto, et al.
Published: (2026)

An $O(n\log n)$ Algorithm for Single-Item Lot Sizing with a One-Breakpoint All-Units Discount and Non-Increasing Prices
by: Papadopoulos, Kleitos
Published: (2025)

Lower Bounds on Adaptive Sensing for Matrix Recovery
by: Kacham, Praneeth, et al.
Published: (2023)

A Simple, Nearly-Optimal Algorithm for Differentially Private All-Pairs Shortest Distances
by: Campbell, Jesse, et al.
Published: (2024)

Lower Bounds for Testing Directed Acyclicity in the Unidirectional Bounded-Degree Model
by: Yoshida, Yuichi
Published: (2026)

A Near-Optimal Offline Algorithm for Dynamic All-Pairs Shortest Paths in Planar Digraphs
by: Das, Debarati, et al.
Published: (2026)

All-Hops Shortest Paths
by: Williams, Virginia Vassilevska, et al.
Published: (2024)

Lower Bounds on $0$-Extension with Steiner Nodes
by: Chen, Yu, et al.
Published: (2024)

Double Exponential Lower Bound for Telephone Broadcast
by: Tale, Prafullkumar
Published: (2024)

Lower Bounds on Flow Sparsifiers with Steiner Nodes
by: Chen, Yu, et al.
Published: (2026)

Fine Grained Lower Bounds for Multidimensional Knapsack
by: Doron-Arad, Ilan, et al.
Published: (2024)

Lower Bounds for Private Estimation of Gaussian Covariance Matrices under All Reasonable Parameter Regimes
by: Portella, Victor S., et al.
Published: (2024)

Optimal Single-Pass Streaming Lower Bounds for Approximating CSPs
by: Singer, Noah G., et al.
Published: (2026)

Improved Lower Bounds for Privacy under Continual Release
by: Aryanfard, Bardiya, et al.
Published: (2025)

Non-Signaling Locality Lower Bounds for Dominating Set
by: Fleming, Noah, et al.
Published: (2026)

A Lower Bound for Light Spanners in General Graphs
by: Bodwin, Greg, et al.
Published: (2024)

Upper and Lower Bounds on the Smoothed Complexity of the Simplex Method
by: Huiberts, Sophie, et al.
Published: (2022)

Lower Bounds on Tree Covers
by: Chen, Yu, et al.
Published: (2025)

Tight Lower Bounds for Central String Queries in Compressed Space
by: Kempa, Dominik, et al.
Published: (2025)

A Tight Lower Bound for Cycle Detection in Grid Graphs
by: Au, Andrew
Published: (2026)

Subsequences With Generalised Gap Constraints: Upper and Lower Complexity Bounds
by: Manea, Florin, et al.
Published: (2024)

Additive Spanner Lower Bounds with Optimal Inner Graph Structure
by: Bodwin, Greg, et al.
Published: (2024)

Improved Lower Bounds on the Expected Length of Longest Common Subsequences
by: Heineman, George T., et al.
Published: (2024)

Lower Bounds for Approximate (& Exact) k-Disjoint-Shortest-Paths
by: Chitnis, Rajesh, et al.
Published: (2024)

Lower Bounds for Matroid Optimization Problems with a Linear Constraint
by: Doron-Arad, Ilan, et al.
Published: (2023)