Copertina

Streaming Complexity Separations for Dense and Sparse Graphs

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Liu, Yang P., Nguyen, Hoai-An, Singer, Noah G., Woodruff, David P.
Natura:	Preprint
Pubblicazione:	2026
Soggetti:	Data Structures and Algorithms Computational Complexity
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

Streaming approximation resistance of every ordering CSP
di: Singer, Noah G., et al.
Pubblicazione: (2021)

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

A New Information Complexity Measure for Multi-pass Streaming with Applications
di: Braverman, Mark, et al.
Pubblicazione: (2024)

Nine lower bound conjectures on streaming approximation algorithms for CSPs
di: Singer, Noah G.
Pubblicazione: (2025)

Sketching approximations and LP approximations for finite CSPs are related
di: Singer, Noah G., et al.
Pubblicazione: (2025)

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

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

Semi-Streaming Algorithms for Graph Property Certification
di: Das, Avinandan, et al.
Pubblicazione: (2025)

Coloring Graphs with Few Colors in the Streaming Model
di: Assadi, Sepehr, et al.
Pubblicazione: (2025)

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

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

Maximization of Approximately Submodular Functions
di: Horel, Thibaut, et al.
Pubblicazione: (2024)

Turnstile Streaming Algorithms Might (Still) as Well Be Linear Sketches, for Polynomial-Length Streams
di: Jiang, Cheng, et al.
Pubblicazione: (2026)

Placing Green Bridges Optimally, with Close-Range Habitats in Sparse Graphs
di: Wallisch, Christian, et al.
Pubblicazione: (2025)

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

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

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

Unbiased Insights: Optimal Streaming Algorithms for $\ell_p$ Sampling, the Forget Model, and Beyond
di: Lin, Honghao, et al.
Pubblicazione: (2025)

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

On the Complexity of Establishing Hereditary Graph Properties via Vertex Splitting
di: Firbas, Alexander, et al.
Pubblicazione: (2024)

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

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

Streaming Zero-Knowledge Proofs
di: Cormode, Graham, et al.
Pubblicazione: (2023)

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

Deterministic Independent Sets in the Semi-Streaming Model
di: Ye, Daniel
Pubblicazione: (2025)

Adversarially Robust Dense-Sparse Tradeoffs via Heavy-Hitters
di: Woodruff, David P., et al.
Pubblicazione: (2024)

Characterizing Streaming Decidability of CSPs via Non-Redundancy
di: Sharma, Amatya, et al.
Pubblicazione: (2026)

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

Tight Streaming Lower Bounds for Deterministic Approximate Counting
di: Wang, Yichuan
Pubblicazione: (2024)

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

A Dichotomy Theorem for Multi-Pass Streaming CSPs
di: Fei, Yumou, et al.
Pubblicazione: (2025)

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

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

Parameterized Complexity of Streaming Diameter and Connectivity Problems
di: Oostveen, Jelle J., et al.
Pubblicazione: (2022)

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

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

Connectivity-Preserving Important Separators: A Framework for Cut-Uncut Problems
di: Kenig, Batya
Pubblicazione: (2025)

On Sketching Trimmed Statistics
di: Lin, Honghao, et al.
Pubblicazione: (2025)

The Complexity of Transitively Orienting Temporal Graphs
di: Mertzios, George B., et al.
Pubblicazione: (2021)

Complexity of Paired Domination Problems on Circle and $k$-Polygon Graphs
di: Mu, Ta-Yu, et al.
Pubblicazione: (2024)