Title: Complexity of strong approximation on the sphere,
Abstract: By assuming some widely-believed arithmetic conjectures, we show that the
task of accepting a number that is representable as a sum of $d\geq2$ 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.