Cover Image

Unifying the Landscape of Super-Logarithmic Dynamic Cell-Probe Lower Bounds

Fuente: arXiv

Saved in:

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

Similar Items

An $Ω( (\log n / \log \log n)^2 )$ Cell-Probe Lower Bound for Dynamic Boolean Data Structures
by: Ko, Young Kun
Published: (2026)

Lower Bounds for Linear Operators
by: Ko, Young Kun
Published: (2025)

Lower Bounds for Convexity Testing
by: Chen, Xi, et al.
Published: (2024)

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

Non-Boolean OMv: One More Reason to Believe Lower Bounds for Dynamic Problems
by: Hu, Bingbing, et al.
Published: (2024)

Treedepth Inapproximability and Exponential ETH Lower Bound
by: Bonnet, Édouard, et al.
Published: (2025)

Cell-Probe Lower Bounds via Semi-Random CSP Refutation: Simplified and the Odd-Locality Case
by: Guruswami, Venkatesan, et al.
Published: (2025)

Multi-Pass Streaming Lower Bounds for Uniformity Testing
by: Li, Qian, et al.
Published: (2025)

Tight Streaming Lower Bounds for Deterministic Approximate Counting
by: Wang, Yichuan
Published: (2024)

Linear Space Streaming Lower Bounds for Approximating CSPs
by: Chou, Chi-Ning, et al.
Published: (2021)

Near-Optimal Space Lower Bounds for Streaming CSPs
by: Fei, Yumou, et al.
Published: (2026)

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

Tight Space Lower Bound for Pseudo-Deterministic Approximate Counting
by: Grossman, Ofer, et al.
Published: (2023)

Polynomial Pass Semi-Streaming Lower Bounds for K-Cores and Degeneracy
by: Assadi, Sepehr, et al.
Published: (2024)

A Tight Double-Exponentially Lower Bound for High-Multiplicity Bin Packing
by: Jansen, Klaus, et al.
Published: (2025)

Automated Lower Bounds for Small Matrix Multiplication Complexity over Finite Fields
by: Wang, Chengu
Published: (2026)

Sampling Permutations with Cell Probes is Hard
by: Alekseev, Yaroslav, et al.
Published: (2025)

On the Advantage of Adaptivity for Sampling with Cell Probes
by: Byramji, Farzan, et al.
Published: (2026)

A Polynomial Space Lower Bound for Diameter Estimation in Dynamic Streams
by: Khanna, Sanjeev, et al.
Published: (2025)

On the (Classical and Quantum) Fine-Grained Complexity of Approximate CVP and Max-Cut
by: Huang, Jeremy Ahrens, et al.
Published: (2024)

Stable Algorithms Lower Bounds for Estimation
by: Yu, Xifan, et al.
Published: (2026)

Self-referential instances of the dominating set problem are irreducible
by: Zhou, Guangyan
Published: (2026)

The Parameterized Landscape of Labeled Graph Contractions
by: Lafond, Manuel, et al.
Published: (2025)

Approximating Klee's Measure Problem and a Lower Bound for Union Volume Estimation
by: Bringmann, Karl, et al.
Published: (2024)

Almost-Optimal Upper and Lower Bounds for Clustering in Low Dimensional Euclidean Spaces
by: Cohen-Addad, Vincent, et al.
Published: (2026)

The Structural Complexity Landscape of Finding Balance-Fair Shortest Paths
by: Bentert, Matthias, et al.
Published: (2024)

Multi-Pass Streaming Lower Bounds for Approximating Max-Cut
by: Fei, Yumou, et al.
Published: (2025)

Kidney Exchange: Faster Parameterized Algorithms and Tighter Lower Bounds
by: Banik, Aritra, et al.
Published: (2025)

Kernelization Bounds for Constrained Coloring
by: Haviv, Ishay
Published: (2026)

Clustering with Locally Bounded Ignorance
by: Garvardt, Jaroslav, et al.
Published: (2026)

The Structure of In-Place Space-Bounded Computation
by: Cook, James, et al.
Published: (2025)

Residue Domination in Bounded-Treewidth Graphs
by: Greilhuber, Jakob, et al.
Published: (2024)

Improved Space Bounds for Subset Sum
by: Belova, Tatiana, et al.
Published: (2024)

Tight Complexity Bounds for Counting Generalized Dominating Sets in Bounded-Treewidth Graphs Part I: Algorithmic Results
by: Focke, Jacob, et al.
Published: (2022)

Lower bounds on pure dynamic programming for connectivity problems on graphs of bounded path-width
by: Kluk, Kacper, et al.
Published: (2025)

On the complexity and approximability of Bounded access Lempel Ziv coding
by: Cicalese, Ferdinando, et al.
Published: (2024)

Structural Parameterizations for Two Bounded Degree Problems Revisited
by: Lampis, Michael, et al.
Published: (2023)

Bounded Independence Edge Sampling for Combinatorial Graph Properties
by: Putterman, Aaron, et al.
Published: (2026)

Better Bounds for Semi-Streaming Single-Source Shortest Paths
by: Assadi, Sepehr, et al.
Published: (2025)

Fundamental Problems on Bounded-Treewidth Graphs: The Real Source of Hardness
by: Esmer, Barış Can, et al.
Published: (2024)