3 papers
cs.DS2026
New Algorithms and Hardness Results for Robust Satisfiability of (Promise) CSPs
Joshua Brakensiek, Lorenzo Ciardo, Venkatesan Guruswami +2
In this paper, we continue the study of robust satisfiability of promise CSPs (PCSPs), initiated in (Brakensiek, Guruswami, Sandeep, STOC 2023 / Discrete Analysis 2025), and obtain…
cs.CC2025
MAX BISECTION might be harder to approximate than MAX CUT
Joshua Brakensiek, Neng Huang, Aaron Potechin +1
The MAX BISECTION problem seeks a maximum-size cut that evenly divides the vertices of a given undirected graph. An open problem raised by Austrin, Benabbas, and Georgiou is whethe…
math.PR2024
Hardness of sampling for the anti-ferromagnetic Ising model on random graphs
Neng Huang, Will Perkins, Aaron Potechin
We prove a hardness of sampling result for the anti-ferromagnetic Ising model on random graphs of average degree for large constant , proving that when the normalized invers…