Bit-complexity estimates in geometric programming, and application to the polynomial-time computation of the spectral radius of nonnegative tensors

Shmuel Friedland, Stéphane Gaubert

Published 2023-01-25Version 1

We show that the spectral radius of nonnegative tensors can be approximated within $\varepsilon$ error in polynomial time. This implies that the maximum of a nonnegative homogeneous $d$-form in the unit ball with respect to $d$-H\"older norm can be approximated in polynomial time. These results are deduced by establishing bit-size estimates for the near-minimizers of functions given by suprema of finitely many log-Laplace transforms of discrete nonnegative measures on $\mathbb{R}^n$. Hence, some known upper bounds for the clique number of hypergraphs are polynomially computable.