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.