Cover Image

Cut-Query Algorithms with Few Rounds

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Kenneth-Mordoch, Yotam, Krauthgamer, Robert
Format:	Preprint
Published:	2025
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

All-Pairs Minimum Cut using $\tilde{O}(n^{7/4})$ Cut Queries
by: Kenneth-Mordoch, Yotam, et al.
Published: (2025)

Faster All-Pairs Minimum Cut: Bypassing Exact Max-Flow
by: Kenneth-Mordoch, Yotam, et al.
Published: (2025)

Simple Algorithms for Fully Dynamic Edge Connectivity
by: Kenneth-Mordoch, Yotam, et al.
Published: (2025)

Faster Pseudo-Deterministic Minimum Cut
by: Kenneth-Mordoch, Yotam
Published: (2026)

Cut Sparsification and Succinct Representation of Submodular Hypergraphs
by: Kenneth, Yotam, et al.
Published: (2023)

On the Adversarial Robustness of Online Importance Sampling
by: Kenneth-Mordoch, Yotam, et al.
Published: (2025)

Sketching Cuts in Graphs and Hypergraphs
by: Kogan, Dmitry, et al.
Published: (2014)

Stable coresets: Unleashing the power of uniform sampling
by: Carmel, Amir, et al.
Published: (2025)

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

Improved Approximation Algorithms for Multiway Cut by Large Mixtures of New and Old Rounding Schemes
by: Brakensiek, Joshua, et al.
Published: (2026)

Minimum $s$--$t$ Cuts with Fewer Cut Queries
by: Jiang, Yonggang, et al.
Published: (2025)

On Solving Linear Systems in Sublinear Time
by: Andoni, Alexandr, et al.
Published: (2018)

Moderate Dimension Reduction for $k$-Center Clustering
by: Jiang, Shaofeng H. -C., et al.
Published: (2023)

On Approximation of Robust Max-Cut and Related Problems using Randomized Rounding Algorithms
by: Shi, Haoyan, et al.
Published: (2024)

An Algorithmic Bridge Between Hamming and Levenshtein Distances
by: Goldenberg, Elazar, et al.
Published: (2022)

Coresets for Kernel Clustering
by: Jiang, Shaofeng H. -C., et al.
Published: (2021)

Near-Optimal Dimension Reduction for Facility Location
by: Huang, Lingxiao, et al.
Published: (2024)

New Oracles and Labeling Schemes for Vertex Cut Queries
by: Jiang, Yonggang, et al.
Published: (2025)

Fast Nearest Neighbor Search for $\ell_p$ Metrics
by: Krauthgamer, Robert, et al.
Published: (2026)

Deterministic Edge Connectivity and Max Flow using Subquadratic Cut Queries
by: Anand, Aditya, et al.
Published: (2024)

Dimension Reduction for Clustering: The Curious Case of Discrete Centers
by: Jiang, Shaofeng H. -C., et al.
Published: (2025)

The Query Complexity of Local Search and Brouwer in Rounds
by: Brânzei, Simina, et al.
Published: (2020)

Streaming Algorithms via Local Algorithms for Maximum Directed Cut
by: Saxena, Raghuvansh R., et al.
Published: (2024)

Clustering Permutations: New Techniques with Streaming Applications
by: Chakraborty, Diptarka, et al.
Published: (2022)

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)

On Sketching Quadratic Forms
by: Andoni, Alexandr, et al.
Published: (2015)

The Query Complexity of Local Search in Rounds on General Graphs
by: Brânzei, Simina, et al.
Published: (2026)

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

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

Comparison of Hyperplane Rounding for Max-Cut and Quantum Approximate Optimization Algorithm over Certain Regular Graph Families
by: Tate, Reuben, et al.
Published: (2025)

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

The Power of Recursive Embeddings for $\ell_p$ Metrics
by: Krauthgamer, Robert, et al.
Published: (2025)

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

Space-Efficient Algorithm for Integer Programming with Few Constraints
by: Rohwedder, Lars, et al.
Published: (2024)

Algorithms for Optimizing Acyclic Queries
by: Luo, Zheng, et al.
Published: (2025)

Fully Scalable MPC Algorithms for Clustering in High Dimension
by: Czumaj, Artur, et al.
Published: (2023)

Constant-Stretch Rounding on the Hypersimplex
by: Anari, Nima, et al.
Published: (2026)

The General Expiration Streaming Model: Diameter, $k$-Center, Counting, Sampling, and Friends
by: Blank, Lotte, et al.
Published: (2025)

Randomized Rounding over Dynamic Programs
by: Bamas, Etienne, et al.
Published: (2025)