NP-hardness of p-adic linear regression

Abstract

$p$-adic linear regression is the problem of finding coefficients ${\hat{I}}^2$ that minimise ${\sum }_i|y_i-x_i^{\top }{\hat{I}}^2{|}_p$. We prove that computing an optimal solution is NP-hard via a polynomial-time reduction from Max Cut using a regularisation gadget.

9 pages