Buchumschlag

Lower Bound Techniques in the Comparison-Query Model and Inversion Minimization on Trees

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Hu, Ivan, van Melkebeek, Dieter, Morgan, Andrew
Format:	Preprint
Veröffentlicht:	2022
Schlagworte:	Data Structures and Algorithms
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

From Dynamic Programs to Greedy Algorithms
von: van Melkebeek, Dieter
Veröffentlicht: (2025)

Tight Lower Bounds for Central String Queries in Compressed Space
von: Kempa, Dominik, et al.
Veröffentlicht: (2025)

Tight Pair Query Lower Bounds for Matching and Earth Mover's Distance
von: Azarmehr, Amir, et al.
Veröffentlicht: (2025)

Sublinear-Time Lower Bounds for Approximating Matching Size using Non-Adaptive Queries
von: Shah, Vihan
Veröffentlicht: (2026)

A Tight Lower Bound for Cycle Detection in Grid Graphs
von: Au, Andrew
Veröffentlicht: (2026)

Statistical Query Lower Bounds for Smoothed Agnostic Learning
von: Diakonikolas, Ilias, et al.
Veröffentlicht: (2026)

Lower Bounds on Tree Covers
von: Chen, Yu, et al.
Veröffentlicht: (2025)

Grammar Boosting: A New Technique for Proving Lower Bounds for Computation over Compressed Data
von: De, Rajat, et al.
Veröffentlicht: (2023)

Lower Bounds for Testing Directed Acyclicity in the Unidirectional Bounded-Degree Model
von: Yoshida, Yuichi
Veröffentlicht: (2026)

Improved Lower Bounds on the Expected Length of Longest Common Subsequences
von: Heineman, George T., et al.
Veröffentlicht: (2024)

Bounded Weighted Edit Distance: Dynamic Algorithms and Matching Lower Bounds
von: Boneh, Itai, et al.
Veröffentlicht: (2025)

New Algorithms and Lower Bounds for Streaming Tournaments
von: Ghosh, Prantar, et al.
Veröffentlicht: (2024)

Lower Bounds on $0$-Extension with Steiner Nodes
von: Chen, Yu, et al.
Veröffentlicht: (2024)

Double Exponential Lower Bound for Telephone Broadcast
von: Tale, Prafullkumar
Veröffentlicht: (2024)

Lower Bounds on Flow Sparsifiers with Steiner Nodes
von: Chen, Yu, et al.
Veröffentlicht: (2026)

Dynamic PageRank: Algorithms and Lower Bounds
von: Jayaram, Rajesh, et al.
Veröffentlicht: (2024)

Fine Grained Lower Bounds for Multidimensional Knapsack
von: Doron-Arad, Ilan, et al.
Veröffentlicht: (2024)

Encodings for Range Minimum Queries over Bounded Alphabets
von: Jo, Seungbum, et al.
Veröffentlicht: (2026)

A General Technique for Searching in Implicit Sets via Function Inversion
von: Aronov, Boris, et al.
Veröffentlicht: (2023)

Upper and Lower Bounds on the Smoothed Complexity of the Simplex Method
von: Huiberts, Sophie, et al.
Veröffentlicht: (2022)

Improved Lower Bounds for Privacy under Continual Release
von: Aryanfard, Bardiya, et al.
Veröffentlicht: (2025)

Non-Signaling Locality Lower Bounds for Dominating Set
von: Fleming, Noah, et al.
Veröffentlicht: (2026)

Lower Bounds for Non-adaptive Local Computation Algorithms
von: Azarmehr, Amir, et al.
Veröffentlicht: (2025)

A Lower Bound for Light Spanners in General Graphs
von: Bodwin, Greg, et al.
Veröffentlicht: (2024)

Pareto Sums of Pareto Sets: Lower Bounds and Algorithms
von: Funke, Daniel, et al.
Veröffentlicht: (2024)

Statistical Query Lower Bounds for Learning Truncated Gaussians
von: Diakonikolas, Ilias, et al.
Veröffentlicht: (2024)

Subsequences With Generalised Gap Constraints: Upper and Lower Complexity Bounds
von: Manea, Florin, et al.
Veröffentlicht: (2024)

Tight Static Lower Bounds for Non-Adaptive Data Structures
von: Persiano, Giuseppe, et al.
Veröffentlicht: (2020)

Additive Spanner Lower Bounds with Optimal Inner Graph Structure
von: Bodwin, Greg, et al.
Veröffentlicht: (2024)

Lower Bounds for Approximate (& Exact) k-Disjoint-Shortest-Paths
von: Chitnis, Rajesh, et al.
Veröffentlicht: (2024)

Lower Bounds for Matroid Optimization Problems with a Linear Constraint
von: Doron-Arad, Ilan, et al.
Veröffentlicht: (2023)

Simplified Tight Bounds for Monotone Minimal Perfect Hashing
von: Kosolobov, Dmitry
Veröffentlicht: (2024)

Online Matrix Factorization, Online Private Query Release, and Online Discrepancy Minimization
von: Nikolov, Aleksandar, et al.
Veröffentlicht: (2026)

Bounding the Average Move Structure Query for Faster and Smaller RLBWT Permutations
von: Brown, Nathaniel K., et al.
Veröffentlicht: (2026)

A Tight Lower Bound for Comparison-Based Quantile Summaries
von: Cormode, Graham, et al.
Veröffentlicht: (2019)

Tight Lower Bounds for Directed Cut Sparsification and Distributed Min-Cut
von: Cheng, Yu, et al.
Veröffentlicht: (2024)

Oblivious Algorithms for Maximum Directed Cut: New Upper and Lower Bounds
von: Hwang, Samuel, et al.
Veröffentlicht: (2024)

New Lower Bounds in Merlin-Arthur Communication and Graph Streaming Verification
von: Ghosh, Prantar, et al.
Veröffentlicht: (2024)

Query Lower Bounds for Diffusion Sampling
von: Xun, Zhiyang, et al.
Veröffentlicht: (2026)

Improved Bounds for High-Dimensional Equivalence and Product Testing using Subcube Queries
von: Adar, Tomer, et al.
Veröffentlicht: (2024)