Hardness of a spectral-norm condition number for absolute value equations

The paper proves NP-hardness, under a polynomial-time many-one reduction, of
deciding whether the maximum spectral norm of $(A - \operatorname{diag} d)^{-1}$
over $d \in [-1, 1]^n$, a condition number for absolute value equations, is
at least a rational threshold. Hardness holds for integer upper-triangular
$A$ with every diagonal entry equal to $2$, for which the entire diagonal
perturbation family is automatically regular, and the decision problem
restricted to rational upper-triangular matrices with this diagonal is
NP-complete. The reduction is from MAX-CUT: for a block upper-triangular
matrix built from an oriented incidence matrix of the graph, the largest
norm of one block of the inverse over the perturbations is proportional to
the square root of the maximum cut size, and the other blocks are of lower
order. For membership in NP, a guessed sign vector $s$ is a certificate:
with $M = A - \operatorname{diag} s$, $\|M^{-1}\|_2 \ge t$ exactly when
$t^2 M^{\mathsf T}M - I$ is not positive definite, which Sylvester's criterion
checks in exact arithmetic.