## Shayan Oveis GharanAssociate ProfessorComputer Science and Engineering University of Washington A short bio and my CV |

I am mainly interested in the design and analysis of algorithms using algebraic techniques.

I am looking for strong Postdocs in Winter or Fall 2023. Please send me an email if you are looking for a position.

In Spring 2019 I co-organized a semester long program on Geometry of Polynomials. Here is a research vignette about my works on Log-concave polynomials with connections to the Geometry of Polynomials program.

A. Karlin, N. Klein, S. Oveis Gharan, A (Slightly) Improved Deterministic Approximation Algorithm for Metric TSP, submitted, 2022.

A. Abdolazimi, S. Oveis Gharan, An Improved Trickle-Down Theorem for Partite Complexes, 2022.

D. Abdolazimi, A. Karlin, N. Klein, S. Oveis Gharan, Matroid Partition Property and the Secretary Problem, ITCS 2023.

D. Abdolazimi, K. Liu, S. Oveis Gharan, A Matrix Trickle-Down Theorem on Simplicial Complexes and Applications to Sampling Colorings, FOCS 2021.

A. Karlin, N. Klein, S. Oveis Gharan, A (Slightly) Improved Bound on the Integrality Gap of the Subtour LP for TSP, FOCS 2022.

F. Ebrahimnejad, A. Nagda, S. Oveis Gharan Counting and Sampling Perfect Matchings in Regular Expanding Non-Bipartite Graphs, ITCS 2022.

A. Karlin, N. Klein, S. Oveis Gharan, X. Zhang An Improved Approximation Algorithm for the Minimum k-Edge Connected Multi-Subgraph Problem, STOC 2022.

N. Anari, K. Liu, S. Oveis Gharan, Cynthia Vinzant, T. Vuong, Log-Concave Polynomials IV: Approximate Exchange, Tight Mixing Times, and Near-Optimal Sampling of Forests, STOC 2021.

A. Karlin, N. Klein, S. Oveis Gharan, A (Slightly) Improved Approximation Algorithm for Metric TSP, STOC 2021.

N. Anari, K. Liu, S. Oveis Gharan, Spectral Independence in High-Dimensional Expanders and Applications to the Hardcore Model, FOCS 2020, invited to special issue.

N. Anari, K. Liu, S. Oveis Gharan, C. Vinzant, Log-Concave Polynomials III: Mason's Ultra-Log-Concavity Conjecture for Independent Sets of Matroids, submitted, 2018.

N. Anari, K. Liu, S. Oveis Gharan, C. Vinzant, Log-Concave Polynomials II: High-Dimensional Walks and an FPRAS for Counting Bases of a Matroid, STOC 2019.

N. Anari, S. Oveis Gharan, C. Vinzant, Log-Concave Polynomials I: Entropy and a Deterministic Approximation Algorithm for Counting Bases of Matroids, FOCS 2018.

N. Anari, S. Oveis Gharan, Effective-Resistance-Reducing Flows, Spectrally Thin Trees, and Asymmetric TSP. See also our recent extension of the proof of Kadison-Singer conjecture by Marcus, Spielman, and Srivastava. See this note for a somewhat short exposition of the ideas. Also, here are short and long presentations of the ideas of the paper. See here for a nice article by Dana Mackenzie about this article.

S. Oveis Gharan, New Rounding Techniques for the Design and Analysis of Approximation Algorithms , PhD thesis, Stanford 2013, ACM Doctoral Dissertation Award Honorable Mention.

S. Oveis Gharan, A. Saberi, M. Singh, A Randomized Rounding Approach to the Traveling Salesman Problem. , FOCS 2011, best paper award.

J. R. Lee, S. Oveis Gharan, L. Trevisan, Multi-way spectral partitioning and higher-order Cheeger inequalities , STOC 2012, JACM 2014.

A. Asadpour, A. Madry, M. Goemans, S. Oveis Gharan, A. Saberi, An O(log n/ log log n)-approximation Algorithm for the Asymmetric Traveling Salesman Problem , SODA 2010, best paper award.

See here for a- 2022 Simons Investigator Award
- 2021 Presburger Award
- 2021 Jean-Loup Baer Professorship
- 2019 Sloan Fellowship
- 2017 ONR Young Investigator Award
- 2016 10 scientist to watch by Science News
- 2016 NSF Career Award
- 2014 ACM Dissertation Award (honorable mention)
- Best paper award SODA 2010, FOCS 2011, STOC 2019, STOC 2021

** Students / Mentee: **

- Dorna Abdolazimi
- Nathan Klein (co-advised with Anna Karlin)
- Kuikui Liu
- Farzam Ebrahimnejad (co-advised with James Lee)
- Robbie Weber, now at UW (co-advised with Anna Karlin)
- Alireza Rezaei, now at Expedia
- Mert Saglam (co-advised with Paul Beame), now at Google.
- Nima Anari, now at Stanford.

- Modern Spectral Graph Theory, Winter 2022
- The Polynomial Paradigm in Algorithms, Winter 2020
- Counting and Sampling, Fall 2017.
- Recent Developments in Approximation Algorithms (CSE 599), Spring 2015.
- Design and Analysis of Algoirthms I (CSE 521) Spring 2016, Winter 2017, Fall 2018, Fall 2019 Fall 2021.
- Design and Analysis of Algorithms (CSE 421) Winter 2018, Spring 2019, Spring 2020
- Foundations of Computing I (CSE 311)Fall 2015, Fall 2016.

Box 352350,

University of Washington,

Seattle, WA 98195-2350.

(206) 685-2181

email: my_first_name@cs.washington.edu where my_first_name=shayan