Buchumschlag

Fast Leaf-to-Ancestor Minimum Query in the Oracle Model

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Upirvitskiy, Aleksey, Levin, Aleksandr
Format:	Preprint
Veröffentlicht:	2026
Schlagworte:	Data Structures and Algorithms Computational Complexity
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

A Fast Coloring Oracle for Average Case Hypergraphs
von: Marcussen, Cassandra, et al.
Veröffentlicht: (2025)

Better Boosting of Communication Oracles, or Not
von: Harms, Nathaniel, et al.
Veröffentlicht: (2024)

Minimum Stable Cut and Treewidth
von: Lampis, Michael
Veröffentlicht: (2021)

Pseudodeterministic Algorithms for Minimum Cut Problems
von: Agarwala, Aryan, et al.
Veröffentlicht: (2025)

On the Inapproximability of Finding Minimum Monitoring Edge-Geodetic Sets
von: Bilò, Davide, et al.
Veröffentlicht: (2024)

Self-referential instances of the dominating set problem are irreducible
von: Zhou, Guangyan
Veröffentlicht: (2026)

A Subquadratic Two-Party Communication Protocol for Minimum Cost Flow
von: Gholizadeh, Hossein, et al.
Veröffentlicht: (2025)

Improved Hardness and Approximations for Cardinality-Based Minimum $s$-$t$ Cuts Problems in Hypergraphs
von: Adriaens, Florian, et al.
Veröffentlicht: (2024)

The Art of Staying Ahead of Deadlines: Improved Algorithms for the Minimum Tardy Processing Time
von: Stoian, Mihail
Veröffentlicht: (2024)

The Query Complexity of Local Search and Brouwer in Rounds
von: Brânzei, Simina, et al.
Veröffentlicht: (2020)

The Mystery Deepens: On the Query Complexity of Tarski Fixed Points
von: Chen, Xi, et al.
Veröffentlicht: (2026)

The Query Complexity of Local Search in Rounds on General Graphs
von: Brânzei, Simina, et al.
Veröffentlicht: (2026)

No Price Tags? No Problem: Query Strategies for Unpriced Information
von: Nadimpalli, Shivam, et al.
Veröffentlicht: (2025)

Unbounded-width CSPs are Untestable in a Sublinear Number of Queries
von: Fei, Yumou
Veröffentlicht: (2025)

Finding Minimum Distance Preservers: A Parameterized Study
von: Simonov, Kirill, et al.
Veröffentlicht: (2026)

On Stable Cutsets in General and Minimum Degree Constrained Graphs
von: Vroon, Mats, et al.
Veröffentlicht: (2025)

On the Distribution of Unweighted Minimum Knapsack Instances with Large SOS Rank
von: Kurpisz, Adam, et al.
Veröffentlicht: (2026)

On the Constant-Factor Approximability of Minimum Cost Constraint Satisfaction Problems
von: DeHaan, Ian, et al.
Veröffentlicht: (2025)

Quantum Search with In-Place Queries
von: Holman, Blake, et al.
Veröffentlicht: (2025)

Finding a Minimum Spanning Tree with a Small Non-Terminal Set
von: Hanaka, Tesshu, et al.
Veröffentlicht: (2023)

Deterministic Independent Sets in the Semi-Streaming Model
von: Ye, Daniel
Veröffentlicht: (2025)

Coloring Graphs with Few Colors in the Streaming Model
von: Assadi, Sepehr, et al.
Veröffentlicht: (2025)

Space Complexity Dichotomies for Subgraph Finding Problems in the Streaming Model
von: Shih, Yu-Sheng, et al.
Veröffentlicht: (2026)

Sampling from the Hardcore Model on Random Regular Bipartite Graphs above the Uniqueness Threshold
von: Kocurek, Nicholas, et al.
Veröffentlicht: (2026)

Fast and simple multiplication of bounded twin-width matrices
von: Kozma, László, et al.
Veröffentlicht: (2026)

Rate-optimal community detection near the KS threshold via node-robust algorithms
von: Ding, Jingqiu, et al.
Veröffentlicht: (2025)

Cascaded Learned Bloom Filter for Optimal Model-Filter Size Balance and Fast Rejection
von: Sato, Atsuki, et al.
Veröffentlicht: (2025)

Fast quantum algorithm for differential equations
von: Bagherimehrab, Mohsen, et al.
Veröffentlicht: (2023)

Neighborhood-Aware Graph Labeling Problem
von: Shahverdikondori, Mohammad, et al.
Veröffentlicht: (2026)

Lazy Kronecker Product
von: Song, Zhao
Veröffentlicht: (2026)

An Invitation to "Fine-grained Complexity of NP-Complete Problems"
von: Nederlof, Jesper
Veröffentlicht: (2026)

Turnstile Streaming Algorithms Might (Still) as Well Be Linear Sketches, for Polynomial-Length Streams
von: Jiang, Cheng, et al.
Veröffentlicht: (2026)

A fine-grained dichotomy for the center problem on Gromov hyperbolic graphs
von: Ducoffe, Guillaume
Veröffentlicht: (2026)

Automated Lower Bounds for Small Matrix Multiplication Complexity over Finite Fields
von: Wang, Chengu
Veröffentlicht: (2026)

Polynomial-Time Almost Log-Space Tree Evaluation by Catalytic Pebbling
von: Asadi, Vahid R., et al.
Veröffentlicht: (2026)

NP-Hardness and a PTAS for the Pinwheel Problem
von: Kleinberg, Robert, et al.
Veröffentlicht: (2026)

The Parameterized Complexity of Scheduling with Precedence Delays: Shuffle Product and Directed Bandwidth
von: Bodlaender, Hans L., et al.
Veröffentlicht: (2026)

Online Orthogonal Vectors Revisited
von: Gajulapalli, Karthik, et al.
Veröffentlicht: (2026)

Characterizing Streaming Decidability of CSPs via Non-Redundancy
von: Sharma, Amatya, et al.
Veröffentlicht: (2026)

Sublinear-query relative-error testing of halfspaces
von: Chen, Xi, et al.
Veröffentlicht: (2026)