Copertina

Deterministic Independent Sets in the Semi-Streaming Model

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autore principale:	Ye, Daniel
Natura:	Preprint
Pubblicazione:	2025
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

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

Rounding Large Independent Sets on Expanders
di: Bafna, Mitali, et al.
Pubblicazione: (2024)

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

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)

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

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

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

Deterministic factorization of constant-depth algebraic circuits in subexponential time
di: Bhattacharjee, Somnath, et al.
Pubblicazione: (2025)

Tight Space Lower Bound for Pseudo-Deterministic Approximate Counting
di: Grossman, Ofer, et al.
Pubblicazione: (2023)

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

Towards Deterministic Algorithms for Constant-Depth Factors of Constant-Depth Circuits
di: Kumar, Mrinal, 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)

Black-Box Identity Testing of Noncommutative Rational Formulas in Deterministic Quasipolynomial Time
di: Arvind, V., et al.
Pubblicazione: (2023)

Dominating Set Knapsack: Profit Optimization on Dominating Sets
di: Singh, Sipra
Pubblicazione: (2025)

Knapsack with Vertex Cover, Set Cover, and Hitting Set
di: Dey, Palash, et al.
Pubblicazione: (2024)

Bounded Independence Edge Sampling for Combinatorial Graph Properties
di: Putterman, Aaron, et al.
Pubblicazione: (2026)

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

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

Geodetic Set on Graphs of Constant Pathwidth and Feedback Vertex Set Number
di: Tale, Prafullkumar
Pubblicazione: (2025)

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)

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

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

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

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

One Color Makes All the Difference in the Tractability of Partial Coloring in Semi-Streaming
di: Das, Avinandan
Pubblicazione: (2026)

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

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

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

FPT Approximation using Treewidth: Capacitated Vertex Cover, Target Set Selection and Vector Dominating Set
di: Chu, Huairui, et al.
Pubblicazione: (2023)

On the (In)Approximability of the Monitoring Edge Geodetic Set Problem
di: Bilò, Davide, et al.
Pubblicazione: (2025)

Parameterized Max Min Feedback Vertex Set
di: Lampis, Michael, et al.
Pubblicazione: (2023)

On the Inapproximability of Finding Minimum Monitoring Edge-Geodetic Sets
di: Bilò, Davide, et al.
Pubblicazione: (2024)

NP-Completeness of Deterministic Communication Complexity via Relaxed Interlacing
di: Gaspers, Serge, et al.
Pubblicazione: (2025)

Timeline Problems in Temporal Graphs: Vertex Cover vs. Dominating Set
di: Herrmann, Anton, et al.
Pubblicazione: (2025)

Reconstructing Sets of Strings from Their k-way Projections: Algorithms & Complexity
di: Tate, Elise, et al.
Pubblicazione: (2025)

The Parameterized Complexity of Independent Set and More when Excluding a Half-Graph, Co-Matching, or Matching
di: Dreier, Jan, et al.
Pubblicazione: (2026)

Pseudo-Deterministic Construction of Irreducible Polynomials over Finite Fields
di: Rai, Shanthanu S
Pubblicazione: (2024)