Buchumschlag

The Structure of In-Place Space-Bounded Computation

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Cook, James, Ghentiyala, Surendra, Mertz, Ian, Pyne, Edward, Sheffield, Nathan S.
Format:	Preprint
Veröffentlicht:	2025
Schlagworte:	Computational Complexity 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

Efficient Catalytic Graph Algorithms
von: Cook, James, et al.
Veröffentlicht: (2025)

Downward self-reducibility in the total function polynomial hierarchy
von: Gajulapalli, Karthik, et al.
Veröffentlicht: (2025)

Bipartite Matching is in Catalytic Logspace
von: Agarwala, Aryan, et al.
Veröffentlicht: (2025)

Frontier Space-Time Algorithms Using Only Full Memory
von: Chmel, Petr, et al.
Veröffentlicht: (2026)

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

Improved Space Bounds for Subset Sum
von: Belova, Tatiana, et al.
Veröffentlicht: (2024)

Linear Space Streaming Lower Bounds for Approximating CSPs
von: Chou, Chi-Ning, et al.
Veröffentlicht: (2021)

Near-Optimal Space Lower Bounds for Streaming CSPs
von: Fei, Yumou, et al.
Veröffentlicht: (2026)

Tight Space Lower Bound for Pseudo-Deterministic Approximate Counting
von: Grossman, Ofer, et al.
Veröffentlicht: (2023)

Structural Parameterizations for Two Bounded Degree Problems Revisited
von: Lampis, Michael, et al.
Veröffentlicht: (2023)

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

Placing Green Bridges Optimally, with Close-Range Habitats in Sparse Graphs
von: Wallisch, Christian, et al.
Veröffentlicht: (2025)

A Dividing Line for Structural Kernelization of Component Order Connectivity via Distance to Bounded Pathwidth
von: Greilhuber, Jakob, et al.
Veröffentlicht: (2026)

Kernelization Bounds for Constrained Coloring
von: Haviv, Ishay
Veröffentlicht: (2026)

Clustering with Locally Bounded Ignorance
von: Garvardt, Jaroslav, et al.
Veröffentlicht: (2026)

Lower Bounds for Convexity Testing
von: Chen, Xi, et al.
Veröffentlicht: (2024)

Residue Domination in Bounded-Treewidth Graphs
von: Greilhuber, Jakob, et al.
Veröffentlicht: (2024)

Sensitivity Lower Bounds for Approximaiton Algorithms
von: Fleming, Noah, et al.
Veröffentlicht: (2024)

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

Treedepth Inapproximability and Exponential ETH Lower Bound
von: Bonnet, Édouard, et al.
Veröffentlicht: (2025)

Multi-Pass Streaming Lower Bounds for Uniformity Testing
von: Li, Qian, et al.
Veröffentlicht: (2025)

Tight Streaming Lower Bounds for Deterministic Approximate Counting
von: Wang, Yichuan
Veröffentlicht: (2024)

On the complexity and approximability of Bounded access Lempel Ziv coding
von: Cicalese, Ferdinando, et al.
Veröffentlicht: (2024)

Bounded Independence Edge Sampling for Combinatorial Graph Properties
von: Putterman, Aaron, et al.
Veröffentlicht: (2026)

A Polynomial Space Lower Bound for Diameter Estimation in Dynamic Streams
von: Khanna, Sanjeev, et al.
Veröffentlicht: (2025)

Better Bounds for Semi-Streaming Single-Source Shortest Paths
von: Assadi, Sepehr, et al.
Veröffentlicht: (2025)

Optimal Single-Pass Streaming Lower Bounds for Approximating CSPs
von: Singer, Noah G., et al.
Veröffentlicht: (2026)

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

Unifying the Landscape of Super-Logarithmic Dynamic Cell-Probe Lower Bounds
von: Ko, Young Kun
Veröffentlicht: (2025)

Polynomial Pass Semi-Streaming Lower Bounds for K-Cores and Degeneracy
von: Assadi, Sepehr, et al.
Veröffentlicht: (2024)

On the Space Complexity of Online Convolution
von: Andersson, Joel Daniel, et al.
Veröffentlicht: (2025)

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

Smooth Trade-off for Tensor PCA via Sharp Bounds for Kikuchi Matrices
von: Kothari, Pravesh K., et al.
Veröffentlicht: (2025)

A Tight Double-Exponentially Lower Bound for High-Multiplicity Bin Packing
von: Jansen, Klaus, et al.
Veröffentlicht: (2025)

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

From Graph Properties to Graph Parameters: Tight Bounds for Counting on Small Subgraphs
von: Döring, Simon, et al.
Veröffentlicht: (2024)

The Price of Being Partial: Complexity of Partial Generalized Dominating Set on Bounded-Treewidth Graphs
von: Greilhuber, Jakob, et al.
Veröffentlicht: (2025)

Improved Bounds for Twin-Width Parameter Variants with Algorithmic Applications to Counting Graph Colorings
von: Baril, Ambroise, et al.
Veröffentlicht: (2025)

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

Computational Complexity in Property Testing
von: Pinto Jr., Renato Ferreira, et al.
Veröffentlicht: (2025)