Complexity of Strong Approximation on the Sphere

Research output: Contribution to journalArticlepeer-review

3 Scopus citations

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 > 2 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 four squares with some restricted congruence conditions, by assuming a polynomial-time algorithm for factoring integers and Conjecture 1.1. As an application, we develop and implement a deterministic polynomial-time algorithm for navigating Lubotzky, Phillips, Sarnak (LPS) Ramanujan graphs, under the same assumptions.

Original languageEnglish (US)
Pages (from-to)13839-13866
Number of pages28
JournalInternational Mathematics Research Notices
Volume2021
Issue number18
DOIs
StatePublished - Sep 1 2021

All Science Journal Classification (ASJC) codes

  • General Mathematics

Fingerprint

Dive into the research topics of 'Complexity of Strong Approximation on the Sphere'. Together they form a unique fingerprint.

Cite this