:: Library Catalog

Buchumschlag

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Assadi, Sepehr, Hoppenworth, Gary, Sundaresan, Janani
Format:	Preprint
Veröffentlicht:	2025
Schlagworte:	Data Structures and Algorithms Computational Complexity
Online-Zugang:	https://arxiv.org/abs/2507.17841
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Coloring Graphs with Few Colors in the Streaming Model
von: Assadi, Sepehr, et al.
Veröffentlicht: (2025)

Distributed Triangle Detection is Hard in Few Rounds
von: Assadi, Sepehr, et al.
Veröffentlicht: (2025)

Settling the Pass Complexity of Approximate Matchings in Dynamic Graph Streams
von: Assadi, Sepehr, et al.
Veröffentlicht: (2024)

Covering Approximate Shortest Paths with DAGs
von: Assadi, Sepehr, et al.
Veröffentlicht: (2025)

Polynomial Pass Semi-Streaming Lower Bounds for K-Cores and Degeneracy
von: Assadi, Sepehr, et al.
Veröffentlicht: (2024)

Parameterized Shortest Path Reconfiguration
von: Bousquet, Nicolas, et al.
Veröffentlicht: (2024)

A Simple $(1-ε)$-Approximation Semi-Streaming Algorithm for Maximum (Weighted) Matching
von: Assadi, Sepehr
Veröffentlicht: (2023)

The Structural Complexity Landscape of Finding Balance-Fair Shortest Paths
von: Bentert, Matthias, et al.
Veröffentlicht: (2024)

Optimal Single-Pass Streaming Lower Bounds for Approximating CSPs
von: Singer, Noah G., et al.
Veröffentlicht: (2026)

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

Deterministic Independent Sets in the Semi-Streaming Model
von: Ye, Daniel
Veröffentlicht: (2025)

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

The Discrepancy of Shortest Paths
von: Bodwin, Greg, et al.
Veröffentlicht: (2024)

Multi-Pass Streaming Lower Bounds for Uniformity Testing
von: Li, Qian, et al.
Veröffentlicht: (2025)

Tight Streaming Lower Bounds for Deterministic Approximate Counting
von: Wang, Yichuan
Veröffentlicht: (2024)

Linear Space Streaming Lower Bounds for Approximating CSPs
von: Chou, Chi-Ning, et al.
Veröffentlicht: (2021)

Near-Optimal Space Lower Bounds for Streaming CSPs
von: Fei, Yumou, et al.
Veröffentlicht: (2026)

Fundamental Problems on Bounded-Treewidth Graphs: The Real Source of Hardness
von: Esmer, Barış Can, et al.
Veröffentlicht: (2024)

Neighborhood-Aware Graph Labeling Problem
von: Shahverdikondori, Mohammad, et al.
Veröffentlicht: (2026)

Near-Optimality for Single-Source Personalized PageRank
von: Jiang, Xinpeng, et al.
Veröffentlicht: (2025)

The Best Arm Evades: Near-optimal Multi-pass Streaming Lower Bounds for Pure Exploration in Multi-armed Bandits
von: Assadi, Sepehr, et al.
Veröffentlicht: (2023)

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

Better Boosting of Communication Oracles, or Not
von: Harms, Nathaniel, et al.
Veröffentlicht: (2024)

From Chinese Postman to Salesman and Beyond I: Approximating Shortest Tours $δ$-Covering All Points on All Edges
von: Frei, Fabian, et al.
Veröffentlicht: (2024)

A Polynomial Space Lower Bound for Diameter Estimation in Dynamic Streams
von: Khanna, Sanjeev, et al.
Veröffentlicht: (2025)

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

Arborescences and Shortest Path Trees when Colors Matter
von: Ardra, P. S., et al.
Veröffentlicht: (2024)

Streaming Zero-Knowledge Proofs
von: Cormode, Graham, et al.
Veröffentlicht: (2023)

Multi-Pass Streaming Lower Bounds for Approximating Max-Cut
von: Fei, Yumou, et al.
Veröffentlicht: (2025)

One Color Makes All the Difference in the Tractability of Partial Coloring in Semi-Streaming
von: Das, Avinandan
Veröffentlicht: (2026)

Faster Vizing and Near-Vizing Edge Coloring Algorithms
von: Assadi, Sepehr
Veröffentlicht: (2024)

Parameterized Restless Temporal Path
von: Cauvi, Justine, et al.
Veröffentlicht: (2025)

Streaming approximation resistance of every ordering CSP
von: Singer, Noah G., et al.
Veröffentlicht: (2021)

Streaming Complexity Separations for Dense and Sparse Graphs
von: Liu, Yang P., et al.
Veröffentlicht: (2026)

Parameterized Maximum Node-Disjoint Paths
von: Lampis, Michael, et al.
Veröffentlicht: (2024)

A Dichotomy Theorem for Multi-Pass Streaming CSPs
von: Fei, Yumou, et al.
Veröffentlicht: (2025)

Characterizing Streaming Decidability of CSPs via Non-Redundancy
von: Sharma, Amatya, et al.
Veröffentlicht: (2026)

Kernelization Bounds for Constrained Coloring
von: Haviv, Ishay
Veröffentlicht: (2026)

Clustering with Locally Bounded Ignorance
von: Garvardt, Jaroslav, et al.
Veröffentlicht: (2026)

Lower Bounds for Convexity Testing
von: Chen, Xi, et al.
Veröffentlicht: (2024)