Buchumschlag

Frontier Space-Time Algorithms Using Only Full Memory

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Chmel, Petr, Dudeja, Aditi, Koucký, Michal, Mertz, Ian, Rajgopal, Ninad
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

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

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

On the Power of Interactive Proofs for Learning
von: Gur, Tom, et al.
Veröffentlicht: (2024)

Faster Exponential-Time Approximation Algorithms Using Approximate Monotone Local Search
von: Esmer, Barış Can, et al.
Veröffentlicht: (2022)

Exact Algorithms for Distance to Unique Vertex Cover
von: Fioravantes, Foivos, et al.
Veröffentlicht: (2025)

A Note on Rounding Matchings in General Graphs
von: Dudeja, Aditi
Veröffentlicht: (2024)

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

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

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

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

Does Subset Sum Admit Short Proofs?
von: Włodarczyk, Michał
Veröffentlicht: (2024)

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

Keeping a Secret Requires a Good Memory: Space Lower-Bounds for Private Algorithms
von: Epasto, Alessandro, et al.
Veröffentlicht: (2026)

Reducing Isotropy and Volume to KLS: Faster Rounding and Volume Algorithms
von: Jia, He, et al.
Veröffentlicht: (2020)

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

Improved Algorithm for Permutation Testing
von: Zhang, Xiaojin
Veröffentlicht: (2020)

Precoloring extension with demands on paths
von: Das, Arun Kumar, et al.
Veröffentlicht: (2025)

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

Algorithms and Hardness for Estimating Statistical Similarity
von: Bhattacharyya, Arnab, et al.
Veröffentlicht: (2025)

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

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

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

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

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

Semi-Streaming Algorithms for Graph Property Certification
von: Das, Avinandan, et al.
Veröffentlicht: (2025)

Parameterized Algorithms for Editing to Uniform Cluster Graph
von: Gaikwad, Ajinkya, et al.
Veröffentlicht: (2024)

Hardness and Algorithmic Results for Roman \{3\}-Domination
von: Reddy, Sangam Balchandar
Veröffentlicht: (2025)

Capacitated Fair-Range Clustering: Hardness and Approximation Algorithms
von: Gadekar, Ameet, et al.
Veröffentlicht: (2025)

From Amortized to Worst Case Delay in Enumeration Algorithms
von: Capelli, Florent, et al.
Veröffentlicht: (2021)

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)

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

Algorithms for the Diverse-k-SAT problem: the geometry of satisfying assignments
von: Austrin, Per, et al.
Veröffentlicht: (2024)

A Space-space Trade-off for Directed st-Connectivity
von: Edenhofer, Roman
Veröffentlicht: (2026)

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

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

Towards Deterministic Algorithms for Constant-Depth Factors of Constant-Depth Circuits
von: Kumar, Mrinal, et al.
Veröffentlicht: (2024)

Reconstructing Sets of Strings from Their k-way Projections: Algorithms & Complexity
von: Tate, Elise, et al.
Veröffentlicht: (2025)

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