Seminar

In this talk we discuss the complexity of accepting a number that is representable as a sum of d ≥ 2 squares subjected to given congruence conditions.  As an application, we explain our deterministic polynomial time algorithm for finding the shortest possible path between two given diagonal vertices of LPS Ramanujan graphs of bounded degree. We also extends our algorithm to a probabilistic algorithm that finds in polynomial time a short path bounded by 3 log_{k−1} (|G|) + O(log log(|G|)) between any pair of vertices in a k-regular LPS Ramanujan graph G.