Copertina

Single-Pass Streaming CSPs via Two-Tier Sampling

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Azarmehr, Amir, Behnezhad, Soheil, Ferrante, Shane
Natura:	Preprint
Pubblicazione:	2026
Soggetti:	Data Structures and Algorithms
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

Half-Approximating Maximum Dicut in the Streaming Setting
di: Azarmehr, Amir, et al.
Pubblicazione: (2025)

Bipartite Matching in Massive Graphs: A Tight Analysis of EDCS
di: Azarmehr, Amir, et al.
Pubblicazione: (2024)

Stochastic Matching via In-n-Out Local Computation Algorithms
di: Azarmehr, Amir, et al.
Pubblicazione: (2024)

Tight Pair Query Lower Bounds for Matching and Earth Mover's Distance
di: Azarmehr, Amir, et al.
Pubblicazione: (2025)

Lower Bounds for Non-adaptive Local Computation Algorithms
di: Azarmehr, Amir, et al.
Pubblicazione: (2025)

Markov Chains with Rewinding
di: Azarmehr, Amir, et al.
Pubblicazione: (2026)

Massively Parallel Minimum Spanning Tree in General Metric Spaces
di: Azarmehr, Amir, et al.
Pubblicazione: (2024)

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

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

Fully Dynamic Matching and Ordered Ruzsa-Szemerédi Graphs
di: Behnezhad, Soheil, et al.
Pubblicazione: (2024)

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

Approximating Maximum Matching Requires Almost Quadratic Time
di: Behnezhad, Soheil, et al.
Pubblicazione: (2024)

Fully Dynamic (Δ+1) Coloring Against Adaptive Adversaries
di: Behnezhad, Soheil, et al.
Pubblicazione: (2024)

Sublinear Algorithms for TSP via Path Covers
di: Behnezhad, Soheil, et al.
Pubblicazione: (2023)

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

Correlation Clustering Beyond the Pivot Algorithm
di: Behnezhad, Soheil, et al.
Pubblicazione: (2024)

Vizing's Theorem in Near-Linear Time
di: Assadi, Sepehr, et al.
Pubblicazione: (2024)

Vizing's Theorem in Deterministic Almost-Linear Time
di: Assadi, Sepehr, et al.
Pubblicazione: (2025)

Space Complexity of Minimum Cut Problems in Single-Pass Streams
di: Ding, Matthew, et al.
Pubblicazione: (2024)

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

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

Approximation algorithms for satisfiable and nearly satisfiable ordering CSPs
di: Makarychev, Yury
Pubblicazione: (2026)

Complexity of Local Search for CSPs Parameterized by Constraint Difference
di: Anand, Aditya, et al.
Pubblicazione: (2025)

Additive Sparsification of CSPs
di: Pelleg, Eden, et al.
Pubblicazione: (2021)

Brooks' Theorem in Graph Streams: A Single-Pass Semi-Streaming Algorithm for $Δ$-Coloring
di: Assadi, Sepehr, et al.
Pubblicazione: (2022)

Solving Random Planted CSPs below the $n^{k/2}$ Threshold
di: Basu, Arpon, et al.
Pubblicazione: (2025)

Min-CSPs on Complete Instances II: Polylogarithmic Approximation for Min-NAE-3-SAT
di: Anand, Aditya, et al.
Pubblicazione: (2025)

Search-space Reduction for Boolean MinCSPs via Essential Constraints
di: Jansen, Bart M. P., et al.
Pubblicazione: (2026)

Fitting Tree Metrics and Ultrametrics in Data Streams
di: Carmel, Amir, et al.
Pubblicazione: (2025)

Non-Redundancy of Low-Arity Symmetric Boolean CSPs
di: Sharma, Amatya, et al.
Pubblicazione: (2026)

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

List Decoding Expander-Based Codes via Fast Approximation of Expanding CSPs: I
di: Jeronimo, Fernando Granha, et al.
Pubblicazione: (2025)

Tight Bounds for Sparsifying Random CSPs
di: Brakensiek, Joshua, et al.
Pubblicazione: (2025)

Two Linear Passes Are Necessary for Sum-Exclude-Self Under Sublinear Space
di: Au, Andrew
Pubblicazione: (2026)

Weighted Reservoir Sampling With Replacement from Data Streams
di: Meligrana, Adriano, et al.
Pubblicazione: (2024)

Perfect Sampling in Turnstile Streams Beyond Small Moments
di: Woodruff, David P., et al.
Pubblicazione: (2025)

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

Tight Gap-Dependent Memory-Regret Trade-Off for Single-Pass Streaming Stochastic Multi-Armed Bandits
di: Ye, Zichun, et al.
Pubblicazione: (2025)

Deterministic $(1+\varepsilon)$-Approximate Maximum Matching with $\mathsf{poly}(1/\varepsilon)$ Passes in the Semi-Streaming Model and Beyond
di: Fischer, Manuela, et al.
Pubblicazione: (2021)

Unbounded-width CSPs are Untestable in a Sublinear Number of Queries
di: Fei, Yumou
Pubblicazione: (2025)