Shayan Oveis Gharan

Assistant professor

Strongly log concave polynomials, high dimensional simplicial complexes, and an FPRAS for counting Bases of Matroids

  Halls department, Hall 3
  Wednesday, 26 December 2018
  15:15 - 16:15

Abstract

A matroid is an abstract combinatorial object which generalizes the notions of spanning trees, and linearly independent sets of vectors. I will talk about an efficient algorithm based on the Markov Chain Monte Carlo technique to approximately count the number of bases of a matroid. In the proof we establish new connections between high dimensional simplicial complexes, and the field of geometry of polynomials. Based on a joint work with Nima Anari, Kuikui Liu, and Cynthia Vinzant.

Bio

Shayan Oveis Gharan is an assistant professor in the computer science and engineering department at University of Washington.
He received his PhD from the MS&E department at Stanford University in 2013 advised by Amin Saberi and Luca Trevisan.
Before joining UW he spent one and a half years as a postdoctoral Miller Fellow at UC Berkeley where his host was Umesh Vazirani.
He did his undergraduate studies at the Computer Engineering department at Sharif University.

Shayan's research includes Algorithm design, Graph Theory and Applied Probability.
He received ACM doctoral dissertation award honorable mention for his PhD thesis "New Rounding Techniques for the Design and Analysis of Approximation Algorithms" in 2013.
He and his coauthors received best paper awards at SODA 2010 and FOCS 2011 for their works on the Traveling Salesman Problem.