Cover Image

MAX BISECTION might be harder to approximate than MAX CUT

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Brakensiek, Joshua, Huang, Neng, Potechin, Aaron, Zwick, Uri
Format:	Preprint
Published:	2025
Subjects:	Computational Complexity Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

On the Mysteries of MAX NAE-SAT
by: Brakensiek, Joshua, 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)

Hardness of sampling for the anti-ferromagnetic Ising model on random graphs
by: Huang, Neng, et al.
Published: (2024)

New Algorithms and Hardness Results for Robust Satisfiability of (Promise) CSPs
by: Brakensiek, Joshua, et al.
Published: (2026)

Is nasty noise actually harder than malicious noise?
by: Blanc, Guy, et al.
Published: (2025)

A Simpler Exponential-Time Approximation Algorithm for MAX-k-SAT
by: Buhrman, Harry, et al.
Published: (2025)

Faster MAX-CUT on Bounded Threshold Rank Graphs
by: Anderson, Prashanti, et al.
Published: (2025)

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

On Optimal Testing of Linearity
by: Arora, Vipul, et al.
Published: (2024)

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

Self-referential instances of the dominating set problem are irreducible
by: Zhou, Guangyan
Published: (2026)

On approximability of the Permanent of PSD matrices
by: Ebrahimnejad, Farzam, et al.
Published: (2024)

Simple approximation algorithms for Polyamorous Scheduling
by: Biktairov, Yuriy, et al.
Published: (2024)

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

On the complexity and approximability of Bounded access Lempel Ziv coding
by: Cicalese, Ferdinando, et al.
Published: (2024)

On the Constant-Factor Approximability of Minimum Cost Constraint Satisfaction Problems
by: DeHaan, Ian, et al.
Published: (2025)

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

Additive approximation algorithm for geodesic centers in $δ$-hyperbolic graphs
by: Chakraborty, Dibyayan, et al.
Published: (2024)

Reconstructing Sets of Strings from Their k-way Projections: Algorithms & Complexity
by: Tate, Elise, et al.
Published: (2025)

Optimal Parallel Basis Finding in Graphic and Related Matroids
by: Khanna, Sanjeev, et al.
Published: (2025)

An $\widetilde{O} (n^{3/7})$ Round Parallel Algorithm for Matroid Bases
by: Khanna, Sanjeev, et al.
Published: (2026)

Bounded Independence Edge Sampling for Combinatorial Graph Properties
by: Putterman, Aaron, et al.
Published: (2026)

The Robotaxi Placement Problem: Minimizing Expected ETA for Stochastic Demand
by: Caragiannis, Ioannis, et al.
Published: (2026)

Improved girth approximation in weighted undirected graphs
by: Kadria, Avi, et al.
Published: (2025)

Halfspaces are hard to test with relative error
by: Chen, Xi, et al.
Published: (2025)

Sublinear-query relative-error testing of halfspaces
by: Chen, Xi, et al.
Published: (2026)

A note on approximating the average degree of bounded arboricity graphs
by: Eden, Talya, et al.
Published: (2026)

Simulation of Non-Hermitian Hamiltonians with Bivariate Quantum Signal Processing
by: Courtney, Joshua M.
Published: (2026)

Optimal Bounds, Barriers, and Extensions for Non-Hermitian Bivariate Quantum Signal Processing
by: Courtney, Joshua M.
Published: (2026)

On the tractability and approximability of non-submodular cardinality-based $s$-$t$ cut problems in hypergraphs
by: Bengali, Vedangi, et al.
Published: (2024)

A quantum neural network framework for scalable quantum circuit approximation of unitary matrices
by: Sarkar, Rohit Sarma, et al.
Published: (2024)

The Price of Being Partial: Complexity of Partial Generalized Dominating Set on Bounded-Treewidth Graphs
by: Greilhuber, Jakob, et al.
Published: (2025)

The Trichotomy of Regular Property Testing
by: Bathie, Gabriel, et al.
Published: (2025)

Downward self-reducibility in the total function polynomial hierarchy
by: Gajulapalli, Karthik, et al.
Published: (2025)

Tight Additive Sensitivity on LZ-style Compressors and String Attractors
by: Fujie, Yuto, et al.
Published: (2025)

Sublinear-Time Approximation for Graph Frequency Vectors in Hyperfinite Graphs
by: Moroie, Gregory
Published: (2025)

Precoloring extension with demands on paths
by: Das, Arun Kumar, et al.
Published: (2025)

A Subquadratic Two-Party Communication Protocol for Minimum Cost Flow
by: Gholizadeh, Hossein, et al.
Published: (2025)

Timeline Problems in Temporal Graphs: Vertex Cover vs. Dominating Set
by: Herrmann, Anton, et al.
Published: (2025)

Better Bounds for Semi-Streaming Single-Source Shortest Paths
by: Assadi, Sepehr, et al.
Published: (2025)