Complexity of strong approximation on the sphere

DOI10.1093/IMRN/RNZ233MaRDI QIDQ6284045arXivWikidataFDO

Authors Naser T. Sardari

Publication date 8 March 2017

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Distance in graphs (05C12)

Abstract: By assuming some widely-believed arithmetic conjectures, we show that the task of accepting a number that is representable as a sum of $dgeq2$ 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~ ef{cc}. As an application, we develop and implement a deterministic polynomial-time algorithm for navigating LPS Ramanujan graphs, under the same assumptions.

This page was built for publication: Complexity of strong approximation on the sphere

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6284045)