Cover Image

Faster MAX-CUT on Bounded Threshold Rank Graphs

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Anderson, Prashanti, Hopkins, Samuel B., Rajaraman, Amit, Steurer, David
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

Entrywise Low-Rank Approximation and Matrix $p \rightarrow q$ Norms via Global Correlation Rounding
by: Anderson, Prashanti, et al.
Published: (2026)

Additive Approximation Schemes for Low-Dimensional Embeddings
by: Anderson, Prashanti, et al.
Published: (2025)

Learning-Augmented Streaming Algorithms for Approximating MAX-CUT
by: Dong, Yinhao, et al.
Published: (2024)

MAX BISECTION might be harder to approximate than MAX CUT
by: Brakensiek, Joshua, et al.
Published: (2025)

Markov Chains Approximate Message Passing
by: Rajaraman, Amit, et al.
Published: (2025)

Coloring 3-Colorable Graphs with Low Threshold Rank
by: Hsieh, Jun-Ting
Published: (2025)

Faster Algorithms for Schatten-p Low Rank Approximation
by: Kacham, Praneeth, et al.
Published: (2024)

Faster Min-Cost Flow and Approximate Tree Decomposition on Bounded Treewidth Graphs
by: Dong, Sally, et al.
Published: (2023)

PageRank Centrality in Directed Graphs with Bounded In-Degree
by: Thorup, Mikkel, et al.
Published: (2025)

Private Edge Density Estimation for Random Graphs: Optimal, Efficient and Robust
by: Chen, Hongjie, et al.
Published: (2024)

Faster Algorithms for Graph Monopolarity
by: Philip, Geevarghese, et al.
Published: (2024)

Non-Signaling Locality Lower Bounds for Dominating Set
by: Fleming, Noah, et al.
Published: (2026)

Locally Stationary Distributions: A Framework for Analyzing Slow-Mixing Markov Chains
by: Liu, Kuikui, et al.
Published: (2024)

Fast Mixing in Sparse Random Ising Models
by: Liu, Kuikui, et al.
Published: (2024)

Finding Colorings in One-Sided Expanders
by: Buhai, Rares-Darius, et al.
Published: (2025)

Semirandom Planted Clique and the Restricted Isometry Property
by: Błasiok, Jarosław, et al.
Published: (2024)

Improving the Threshold for Finding Rank-1 Matrices in a Subspace
by: Dastidar, Jeshu, et al.
Published: (2025)

Faster Algorithm for Bounded Tree Edit Distance in the Low-Distance Regime
by: Kociumaka, Tomasz, et al.
Published: (2025)

Bounding the Average Move Structure Query for Faster and Smaller RLBWT Permutations
by: Brown, Nathaniel K., et al.
Published: (2026)

Sampling from convex sets with a cold start using multiscale decompositions
by: Narayanan, Hariharan, et al.
Published: (2022)

Multi-Way Co-Ranking: Index-Space Partitioning of Sorted Sequences Without Merge
by: Joshi, Amit
Published: (2025)

On Rotation Distance of Rank Bounded Trees
by: M., Anoop S. K., et al.
Published: (2023)

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

Dynamic PageRank: Algorithms and Lower Bounds
by: Jayaram, Rajesh, et al.
Published: (2024)

Faster MPC Algorithms for Approximate Allocation in Uniformly Sparse Graphs
by: Łącki, Jakub, et al.
Published: (2025)

Faster Approximation Algorithms for Restricted Shortest Paths in Directed Graphs
by: Ashvinkumar, Vikrant, et al.
Published: (2024)

Sample-Optimal Private Regression in Polynomial Time
by: Anderson, Prashanti, et al.
Published: (2025)

Outlier-robust Mean Estimation near the Breakdown Point via Sum-of-Squares
by: Chen, Hongjie, et al.
Published: (2024)

A Faster Algorithm for Maximum Weight Matching on Unrestricted Bipartite Graphs
by: Kwok, Shawxing
Published: (2025)

Improved Approximation for Ranking on General Graphs
by: Derakhshan, Mahsa, et al.
Published: (2025)

Faster Estimation of the Average Degree of a Graph Using Random Edges and Structural Queries
by: Beretta, Lorenzo, et al.
Published: (2025)

Improved Bounds for High-Dimensional Equivalence and Product Testing using Subcube Queries
by: Adar, Tomer, et al.
Published: (2024)

A Simple Analysis of Ranking in General Graphs
by: Derakhshan, Mahsa, et al.
Published: (2025)

Personalized PageRank Estimation in Undirected Graphs
by: Bertram, Christian, et al.
Published: (2026)

Online Edge Coloring: Sharp Thresholds
by: Blikstad, Joakim, et al.
Published: (2025)

Faster Graph Embeddings via Coarsening
by: Fahrbach, Matthew, et al.
Published: (2020)

Almost-Uniform Edge Sampling: Leveraging Independent-Set and Local Graph Queries
by: Adar, Tomer, et al.
Published: (2026)

Simple and Faster Algorithms for Knapsack
by: He, Qizheng, et al.
Published: (2023)

Faster optimal univariate microgaggregation
by: Stamm, Felix I., et al.
Published: (2024)

Faster Parameterized Vertex Multicut
by: Chu, Huairui, et al.
Published: (2026)