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 language | English (US) |
---|---|
Pages (from-to) | 13839-13866 |
Number of pages | 28 |
Journal | International Mathematics Research Notices |
Volume | 2021 |
Issue number | 18 |
DOIs | |
State | Published - Sep 1 2021 |
All Science Journal Classification (ASJC) codes
- General Mathematics