Buchumschlag

A Space-space Trade-off for Directed st-Connectivity

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
1. Verfasser:	Edenhofer, Roman
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

Directed st-connectivity with few paths is in quantum logspace
von: Apers, Simon, et al.
Veröffentlicht: (2024)

Dequantization and Hardness of Spectral Sum Estimation
von: Edenhofer, Roman, et al.
Veröffentlicht: (2025)

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

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

Connectivity-Preserving Important Separators: A Framework for Cut-Uncut Problems
von: Kenig, Batya
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)

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

On the Complexity of Hyperpath and Minimal Separator Enumeration in Directed Hypergraphs
von: Kurita, Kazuhiro, et al.
Veröffentlicht: (2025)

The Structure of In-Place Space-Bounded Computation
von: Cook, James, et al.
Veröffentlicht: (2025)

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

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

Gray Codes With Constant Delay and Constant Auxiliary Space
von: Amarilli, Antoine, et al.
Veröffentlicht: (2026)

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

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

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

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

Subset Sum in Near-Linear Pseudopolynomial Time and Polynomial Space
von: Sajith, Thejas Radhika
Veröffentlicht: (2025)

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

Search-space Reduction for Boolean MinCSPs via Essential Constraints
von: Jansen, Bart M. P., et al.
Veröffentlicht: (2026)

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

Encoding Co-Lex Orders of Finite-State Automata in Linear Space
von: Becker, Ruben, et al.
Veröffentlicht: (2025)

Parameterized Complexity of Streaming Diameter and Connectivity Problems
von: Oostveen, Jelle J., et al.
Veröffentlicht: (2022)

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

A Note on Approximability of Densest At-Least-k-Subgraph
von: Laekhanukit, Bundit, et al.
Veröffentlicht: (2026)

A Dichotomy Theorem for Multi-Pass Streaming CSPs
von: Fei, Yumou, et al.
Veröffentlicht: (2025)

A Simple Proof that Ricochet Robots is PSPACE-Complete
von: Balanza-Martinez, Jose, et al.
Veröffentlicht: (2024)

A Faster Randomized Algorithm for Vertex Cover: An Automated Approach
von: Clinch, Katie, et al.
Veröffentlicht: (2025)

A Complexity Analysis of the c-Closed Vertex Deletion Problem
von: Lehner, Lisa, et al.
Veröffentlicht: (2025)

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

A Unified Approach to Memory-Sample Tradeoffs for Detecting Planted Structures
von: Garg, Sumegha, et al.
Veröffentlicht: (2026)

Clustering Permutations under the Ulam Metric: A Parameterized Complexity Study
von: Bai, Tian, et al.
Veröffentlicht: (2026)

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

A Simpler Exponential-Time Approximation Algorithm for MAX-k-SAT
von: Buhrman, Harry, et al.
Veröffentlicht: (2025)

A tight quasi-polynomial bound for Global Label Min-Cut
von: Jaffke, Lars, et al.
Veröffentlicht: (2022)

A New Information Complexity Measure for Multi-pass Streaming with Applications
von: Braverman, Mark, et al.
Veröffentlicht: (2024)

Conditional lower bounds for sparse parameterized 2-CSP: A streamlined proof
von: S., Karthik C., et al.
Veröffentlicht: (2023)

A constant time complexity algorithm for the unbounded knapsack problem with bounded coefficients
von: Yang, Yang
Veröffentlicht: (2024)

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

A lossless a priori splitting rule for split-delivery routing problems
von: Jones, Bo, et al.
Veröffentlicht: (2025)

A general framework for finding diverse solutions via network flow and its applications
von: Iwamasa, Yuni, et al.
Veröffentlicht: (2025)