Lune

Profiles2020-2025

Shayan Oveis Gharan

University of Washington

10Papers
7Last author
13Unique co-authors
0First author
0Solo

First and last author come from byline position, which some venues assign alphabetically.

Recent papers10

  1. On Approximability of the Permanent of PSD MatricesAuthor 3 of 3STOC 2025 · 1 citation
  2. Optimal Trickle-Down Theorems for Path Complexes via C-Lorentzian Polynomials with Applications to Sampling and Log-Concave SequencesAuthor 3 of 3FOCS 2025 · 1 citation
  3. A (Slightly) Improved Bound on the Integrality Gap of the Subtour LP for TSPAuthor 3 of 3FOCS 2022 · 13 citations
  4. An improved approximation algorithm for the minimum k-edge connected multi-subgraph problemAuthor 3 of 4STOC 2022 · 6 citations
  5. A (slightly) improved approximation algorithm for metric TSPAuthor 3 of 3STOC 2021 · 114 citations
  6. Log-concave polynomials IV: approximate exchange, tight mixing times, and near-optimal sampling of forestsAuthor 3 of 5STOC 2021 · 5 citations
  7. A Matrix Trickle-Down Theorem on Simplicial Complexes and Applications to Sampling ColoringsAuthor 3 of 3FOCS 2021 · 4 citations
  8. Spectral Independence in High-Dimensional Expanders and Applications to the Hardcore ModelAuthor 3 of 3FOCS 2020 · 97 citations
  9. Composable Core-sets for Determinant Maximization Problems via Spectral SpannersAuthor 3 of 4SODA 2020 · 10 citations
  10. An improved approximation algorithm for TSP in the half integral caseAuthor 3 of 3STOC 2020 · 1 citation
Dusk over the sea between two cliffs drawn in fine vertical lines