Imagen de Portada

On the Space Complexity of Online Convolution

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autores principales:	Andersson, Joel Daniel, Yehudayoff, Amir
Formato:	Preprint
Publicado:	2025
Materias:	Computational Complexity Data Structures and Algorithms
Acceso en línea:	Acceder al recurso
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

Ejemplares similares

Space Complexity Dichotomies for Subgraph Finding Problems in the Streaming Model
por: Shih, Yu-Sheng, et al.
Publicado: (2026)

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

Faster Convolutions: Yates and Strassen Revisited
por: Brand, Cornelius, et al.
Publicado: (2025)

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

Multicut Problems in Embedded Graphs: The Dependency of Complexity on the Demand Pattern
por: Focke, Jacob, et al.
Publicado: (2023)

From Chinese Postman to Salesman and Beyond II: Inapproximability and Parameterized Complexity
por: Frei, Fabian, et al.
Publicado: (2025)

Online Orthogonal Vectors Revisited
por: Gajulapalli, Karthik, et al.
Publicado: (2026)

Removable Online Knapsack and Advice
por: Böckenhauer, Hans-Joachim, et al.
Publicado: (2020)

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

Parameterized Complexity of Vehicle Routing
por: Döring, Michelle, et al.
Publicado: (2025)

The Complexity of Finding and Counting Subtournaments
por: Döring, Simon, et al.
Publicado: (2025)

On the Parameterized Complexity of Odd Coloring
por: Bhyravarapu, Sriram, et al.
Publicado: (2025)

On the Complexity of Signed Roman Domination
por: Reddy, Sangam Balchandar
Publicado: (2025)

Computational Complexity in Property Testing
por: Pinto Jr., Renato Ferreira, et al.
Publicado: (2025)

The Complexity of Counting Small Sub-Hypergraphs
por: Bressan, Marco, et al.
Publicado: (2025)

The Complexity of Maximal Common Subsequence Enumeration
por: Buzzega, Giovanni, et al.
Publicado: (2025)

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

The Fine-Grained Complexity of Episode Matching
por: Bille, Philip, et al.
Publicado: (2021)

On the Parameterized Complexity of Min-Sum-Radii
por: Kumar, Pankaj, et al.
Publicado: (2026)

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

From Donkeys to Kings in Tournaments
por: Abboud, Amir, et al.
Publicado: (2024)

Novel Complexity Results for Temporal Separators with Deadlines
por: Dondi, Riccardo, et al.
Publicado: (2025)

Complexity of Local Search for Euclidean Clustering Problems
por: Manthey, Bodo, et al.
Publicado: (2023)

Streaming Complexity Separations for Dense and Sparse Graphs
por: Liu, Yang P., et al.
Publicado: (2026)

The Query Complexity of Local Search and Brouwer in Rounds
por: Brânzei, Simina, et al.
Publicado: (2020)

On the Complexity of Fundamental Problems for DAG-Compressed Graphs
por: Chudigiewitsch, Florian, et al.
Publicado: (2026)

On the Complexity of Hyperpath and Minimal Separator Enumeration in Directed Hypergraphs
por: Kurita, Kazuhiro, et al.
Publicado: (2025)

An Invitation to "Fine-grained Complexity of NP-Complete Problems"
por: Nederlof, Jesper
Publicado: (2026)

The Mystery Deepens: On the Query Complexity of Tarski Fixed Points
por: Chen, Xi, et al.
Publicado: (2026)

The Query Complexity of Local Search in Rounds on General Graphs
por: Brânzei, Simina, et al.
Publicado: (2026)

On the Complexity of 2-club Cluster Editing with Vertex Splitting
por: Abu-Khzam, Faisal N., et al.
Publicado: (2024)

On the Complexity of Minimizing Energy Consumption of Partitioning DAG Tasks
por: Liu, Wei, et al.
Publicado: (2024)

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

Gray Codes With Constant Delay and Constant Auxiliary Space
por: Amarilli, Antoine, et al.
Publicado: (2026)

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

A Complexity Analysis of the c-Closed Vertex Deletion Problem
por: Lehner, Lisa, et al.
Publicado: (2025)

Subset Sum in Near-Linear Pseudopolynomial Time and Polynomial Space
por: Sajith, Thejas Radhika
Publicado: (2025)

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

Settling the Pass Complexity of Approximate Matchings in Dynamic Graph Streams
por: Assadi, Sepehr, et al.
Publicado: (2024)

The Computational Complexity of Avoiding Strict Saddle Points in Constrained Optimization
por: Kontogiannis, Andreas, et al.
Publicado: (2026)