2 papers
cs.CC2024
On the Mysteries of MAX NAE-SAT
Joshua Brakensiek, Neng Huang, Aaron Potechin +1
MAX NAE-SAT is a natural optimization problem, closely related to its better-known relative MAX SAT. The approximability status of MAX NAE-SAT is almost completely understood if al…
math.CO2024
The Spectrum of the Singular Values of Z-Shaped Graph Matrices
Wenjun Cai, Aaron Potechin
Graph matrices are a type of matrix which has played a crucial role in analyzing the sum of squares hierarchy on average case problems. However, except for rough norm bounds, littl…