Cover Image

Streaming Algorithms via Local Algorithms for Maximum Directed Cut

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Saxena, Raghuvansh R., Singer, Noah G., Sudan, Madhu, Velusamy, Santhoshini
Format:	Preprint
Published:	2024
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Oblivious Algorithms for Maximum Directed Cut: New Upper and Lower Bounds
by: Hwang, Samuel, et al.
Published: (2024)

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

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

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

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

Near-optimal streaming approximation for Max-DICUT in sublinear space using two passes
by: Velusamy, Santhoshini
Published: (2025)

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

Optimally detecting uniformly-distributed $\ell_2$ heavy hitters in data streams
by: Velusamy, Santhoshini, et al.
Published: (2025)

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

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

Efficient Algorithms and New Characterizations for CSP Sparsification
by: Khanna, Sanjeev, et al.
Published: (2024)

Near-optimal Size Linear Sketches for Hypergraph Cut Sparsifiers
by: Khanna, Sanjeev, et al.
Published: (2024)

Almost-Tight Bounds on Preserving Cuts in Classes of Submodular Hypergraphs
by: Khanna, Sanjeev, et al.
Published: (2024)

Near-optimal Hypergraph Sparsification in Insertion-only and Bounded-deletion Streams
by: Khanna, Sanjeev, et al.
Published: (2025)

Streaming and Massively Parallel Algorithms for Euclidean Max-Cut
by: Menand, Nicolas, et al.
Published: (2025)

A Theory of Spectral CSP Sparsification
by: Khanna, Sanjeev, et al.
Published: (2025)

New Parallel and Streaming Algorithms for Directed Densest Subgraph
by: Mitrović, Slobodan, et al.
Published: (2025)

Simpler O(1) Query Algorithm for Level Ancestors
by: Saxena, Sanjeev
Published: (2022)

Maximum-Flow and Minimum-Cut Sensitivity Oracles for Directed Graphs
by: Ahi, Mridul, et al.
Published: (2025)

An FPT algorithm for Matching Cut and d-cut
by: Aravind, N R, et al.
Published: (2021)

Cut-Query Algorithms with Few Rounds
by: Kenneth-Mordoch, Yotam, et al.
Published: (2025)

Streaming Algorithms for Connectivity Augmentation
by: Jin, Ce, et al.
Published: (2024)

Streaming Algorithms for Network Design
by: Chekuri, Chandra, et al.
Published: (2025)

Markov Chains with Rewinding
by: Azarmehr, Amir, et al.
Published: (2026)

Matching (Multi)Cut: Algorithms, Complexity, and Enumeration
by: Gomes, Guilherme C. M., et al.
Published: (2024)

A Simple and Fast Algorithm for Fair Cuts
by: Li, Jason, et al.
Published: (2024)

Quality control in sublinear time: a case study via random graphs
by: Marcussen, Cassandra, et al.
Published: (2025)

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

Improved Approximation Algorithm for Maximum Balanced Biclique
by: Manurangsi, Pasin
Published: (2026)

Streaming Algorithms with Few State Changes
by: Jayaram, Rajesh, et al.
Published: (2024)

Semi-Streaming Algorithms for Hypergraph Matching
by: Reinstädtler, Henrik, et al.
Published: (2025)

Streaming Algorithms for Geometric Steiner Forest
by: Czumaj, Artur, et al.
Published: (2020)

Improved Algorithms for Maximum Coverage in Dynamic and Random Order Streams
by: Chakrabarti, Amit, et al.
Published: (2024)

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

Latency Guarantees for Caching with Delayed Hits
by: Gurushankar, Keerthana, et al.
Published: (2025)

New Algorithms and Lower Bounds for Streaming Tournaments
by: Ghosh, Prantar, et al.
Published: (2024)

Streaming Max-Cut in General Metrics
by: Jiang, Shaofeng H. -C., et al.
Published: (2025)

Multiplicative Auction Algorithm for Approximate Maximum Weight Bipartite Matching
by: Zheng, Da Wei, et al.
Published: (2023)

An Improved Approximation Algorithm for Maximum Weight 3-Path Packing
by: Zhao, Jingyang, et al.
Published: (2025)

Towards Metric DBSCAN: Exact, Approximate, and Streaming Algorithms
by: Mo, Guanlin, et al.
Published: (2024)