Buchumschlag

Near-optimal streaming approximation for Max-DICUT in sublinear space using two passes

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
1. Verfasser:	Velusamy, Santhoshini
Format:	Preprint
Veröffentlicht:	2025
Schlagworte:	Data Structures and Algorithms
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Optimally detecting uniformly-distributed $\ell_2$ heavy hitters in data streams
von: Velusamy, Santhoshini, et al.
Veröffentlicht: (2025)

Sketching approximations and LP approximations for finite CSPs are related
von: Singer, Noah G., et al.
Veröffentlicht: (2025)

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

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

Non-Redundancy of Low-Arity Symmetric Boolean CSPs
von: Sharma, Amatya, et al.
Veröffentlicht: (2026)

Oblivious Algorithms for Maximum Directed Cut: New Upper and Lower Bounds
von: Hwang, Samuel, et al.
Veröffentlicht: (2024)

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

Streaming Algorithms via Local Algorithms for Maximum Directed Cut
von: Saxena, Raghuvansh R., et al.
Veröffentlicht: (2024)

Testable algorithms for approximately counting edges and triangles in sublinear time and space
von: Eden, Talya, et al.
Veröffentlicht: (2025)

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

Efficient stream-based Max-Min diversification with minimal failure rate
von: Kalogeratos, Argyris, et al.
Veröffentlicht: (2020)

Fast, robust approximate message passing
von: Ivkov, Misha, et al.
Veröffentlicht: (2024)

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)

Near-optimal hierarchical matrix approximation from matrix-vector products
von: Chen, Tyler, et al.
Veröffentlicht: (2024)

Near-optimal Algorithms for Stochastic Online Bin Packing
von: Ayyadevara, Nikhil, et al.
Veröffentlicht: (2022)

Near-optimal Size Linear Sketches for Hypergraph Cut Sparsifiers
von: Khanna, Sanjeev, et al.
Veröffentlicht: (2024)

Nine lower bound conjectures on streaming approximation algorithms for CSPs
von: Singer, Noah G.
Veröffentlicht: (2025)

Near-optimal Hypergraph Sparsification in Insertion-only and Bounded-deletion Streams
von: Khanna, Sanjeev, et al.
Veröffentlicht: (2025)

Deterministic Edge Connectivity and Max Flow using Subquadratic Cut Queries
von: Anand, Aditya, et al.
Veröffentlicht: (2024)

Permutation patterns in streams
von: Berendsohn, Benjamin Aram
Veröffentlicht: (2025)

Robust Max Selection
von: Dang, Trung, et al.
Veröffentlicht: (2024)

Near-optimal Linear Sketches and Fully-Dynamic Algorithms for Hypergraph Spectral Sparsification
von: Khanna, Sanjeev, et al.
Veröffentlicht: (2025)

Easy, robust approximate message passing for planted spike models
von: Ivkov, Misha, et al.
Veröffentlicht: (2026)

Engineering Semi-streaming DFS algorithms
von: Bhagavan, Kancharla Nikhilesh, et al.
Veröffentlicht: (2024)

Testing frequency distributions in a stream
von: Mathieu, Claire, et al.
Veröffentlicht: (2023)

Max-Min Diversification with Asymmetric Distances
von: Kumpulainen, Iiro, et al.
Veröffentlicht: (2025)

Max-Cut with Multiple Cardinality Constraints
von: Makarychev, Yury, et al.
Veröffentlicht: (2025)

Streaming Max-Cut in General Metrics
von: Jiang, Shaofeng H. -C., et al.
Veröffentlicht: (2025)

Local Max-Cut on Sparse Graphs
von: Schwartzman, Gregory
Veröffentlicht: (2023)

Max-Distance Sparsification for Diversification and Clustering
von: Kumabe, Soh
Veröffentlicht: (2024)

Sum-of-Max Chain Partition of a Tree
von: Luo, Ruixi, et al.
Veröffentlicht: (2025)

Max Cut with Small-Dimensional SDP Solutions
von: Chang, Hsien-Chih, et al.
Veröffentlicht: (2026)

SimiSketch: Efficiently Estimating Similarity of streaming Multisets
von: Dong, Fenghao, et al.
Veröffentlicht: (2024)

Faster Semi-streaming Matchings via Alternating Trees
von: Mitrović, Slobodan, et al.
Veröffentlicht: (2024)

Linear-space LCS enumeration with quadratic-time delay for two strings
von: Sakai, Yoshifumi
Veröffentlicht: (2025)

Streaming and Massively Parallel Algorithms for Euclidean Max-Cut
von: Menand, Nicolas, et al.
Veröffentlicht: (2025)

Faster Weak Expander Decompositions and Approximate Max Flow
von: Fleischmann, Henry, et al.
Veröffentlicht: (2025)

Submodular Max-Min Allocation under Identical Valuations
von: Boehmer, Kimon
Veröffentlicht: (2026)

Robust Multiagent Collaboration Through Weighted Max-Min T-Joins
von: Alipour, Sharareh
Veröffentlicht: (2026)

Efficient parameterized approximation
von: Kratsch, Stefan, et al.
Veröffentlicht: (2025)