Logo

Mathematical Sciences Research Institute

Home » ANT Postdoc Seminar: Complexity of strong approximation on the sphere

Seminar

ANT Postdoc Seminar: Complexity of strong approximation on the sphere April 14, 2017 (11:00 AM PDT - 11:50 AM PDT)
Parent Program:
Location: MSRI: Simons Auditorium
Speaker(s) Naser Sardari (MSRI - Mathematical Sciences Research Institute)
Description No Description
Video
No Video Uploaded
Abstract/Media

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.

No Notes/Supplements Uploaded No Video Files Uploaded