Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

Complexity of strong approximation on the sphere

Algebra & Discrete Mathematics

Speaker: Naser Talebizadeh Sardari, University of Wisconsin
Location: MSB 2112
Start time: Mon, Jun 5 2017, 4:10PM

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.