Complexity of strong approximation on the sphere
arXiv:1703.02709
Abstract
By assuming some widely-believed arithmetic conjectures, we show that the task of accepting a number that is representable as a sum of squares subjected to given congruence conditions is NP-complete. On the other hand, we develop and implement a deterministic polynomial-time algorithm that represents a number as a sum of 4 squares with some restricted congruence conditions, by assuming a polynomial-time algorithm for factoring integers and Conjecture~\ref{cc}. As an application, we develop and implement a deterministic polynomial-time algorithm for navigating LPS Ramanujan graphs, under the same assumptions.
Submitted to Mathematics of Computation