a person in the record
Shayan Oveis Gharan
Computer scientist and academicborn 1986
Wikidata lists 3 doctoral students. Linked to Wikidata, ORCID, and 2 other registers.
How to read the markscited by a repository's recordstated by Wikidata or indexed by OpenAlexclaimed on an ORCID list, or inferred
Students on Wikidata3
From Wikidata, shown separately from the thesis records.
- stated by Wikidata
- stated by Wikidata
- stated by Wikidata
The line above and below
The advisors of their advisors, four steps up at most, in the thesis records and on Wikidata, each kind marked; a person in both is listed once.
Below them, within 3 steps, the record reaches 3 people: 3 stated by Wikidata.
Education and career3
From Wikidata, shown separately from the thesis records. Each place opens its Wikidata item.
- undated
- undatedstudied
- undatedworked
Papers in OpenAlex100
2007most in 2011: 92026
last at University of Washington
writes on Complexity and Algorithms in Graphs, Advanced Graph Theory Research, Optimization and Search Problems, Advanced Combinatorial Mathematics, Game Theory and Voting Systems
- indexed by OpenAlexcited 223
Online Stochastic Matching: Online Actions Based on Offline Statistics
2012 · Mathematics of Operations Research · 3 authors - indexed by OpenAlexcited 179
Multiway Spectral Partitioning and Higher-Order Cheeger Inequalities
2014 · Journal of the ACM · 3 authors - indexed by OpenAlexcited 175
A Randomized Rounding Approach to the Traveling Salesman Problem
2011 · Annual Symposium on Foundations of Computer Science · 3 authors - indexed by OpenAlex2019 · Journal of Political Economy · 3 authorscited 172
- indexed by OpenAlexcited 162
An O (log n /log log n )-approximation Algorithm for the Asymmetric Traveling Salesman Problem
2010 · ACM-SIAM Symposium on Discrete Algorithms (SODA) · 5 authors - indexed by OpenAlexcited 127
A (slightly) improved approximation algorithm for metric TSP
2021 · ACM SIGACT Symposium on Theory of Computing (STOC) · 3 authors - indexed by OpenAlexcited 113
Multi-way spectral partitioning and higher-order cheeger inequalities
2012 · ACM Symposium on Theory of Computing (STOC) · 3 authors - indexed by OpenAlexcited 104
Log-concave polynomials II: high-dimensional walks and an FPRAS for counting bases of a matroid
2019 · ACM SIGACT Symposium on Theory of Computing (STOC) · 4 authors - indexed by OpenAlexcited 100
Spectral Independence in High-Dimensional Expanders and Applications to the Hardcore Model
2020 · Annual Symposium on Foundations of Computer Science · 3 authors - indexed by OpenAlex2011 · ACM-SIAM Symposium on Discrete Algorithms (SODA) · 2 authorscited 81
the 25 most cited of 100
- indexed by OpenAlex2009 · ACM Transactions on Algorithms · 6 authorscited 78
- indexed by OpenAlexcited 67
- indexed by OpenAlexcited 65
Nash Social Welfare for Indivisible Items under Separable, Piecewise-Linear Concave Utilities
2018 · Society for Industrial and Applied Mathematics eBooks · 4 authors - indexed by OpenAlex2013 · ACM Symposium on Theory of Computing (STOC) · 5 authorscited 59
- indexed by OpenAlexcited 53
Approximating the Expansion Profile and Almost Optimal Local Graph Clustering
2012 · Annual Symposium on Foundations of Computer Science · 2 authors - indexed by OpenAlexcited 50
An O(log n/log log n)-Approximation Algorithm for the Asymmetric Traveling Salesman Problem
2017 · Operations Research · 5 authors - indexed by OpenAlex2018 · Annual Symposium on Foundations of Computer Science · 3 authorscited 49
- indexed by OpenAlex2021 · Duke Mathematical Journal · 3 authorscited 45
- indexed by OpenAlexcited 41
Log-concave polynomials II: High-dimensional walks and an FPRAS for counting bases of a matroid
2023 · Annals of Mathematics · 4 authors - indexed by OpenAlexcited 41
A generalization of permanent inequalities and applications in counting and optimization
2017 · ACM SIGACT Symposium on Theory of Computing (STOC) · 2 authors - indexed by OpenAlexcited 41
Nash Social Welfare, Matrix Permanent, and Stable Polynomials
2016 · arXiv (Cornell University) · 4 authors - indexed by OpenAlexcited 39
Simultaneous Approximations for Adversarial and Stochastic Online Budgeted Allocation
2012 · ACM-SIAM Symposium on Discrete Algorithms (SODA) · 3 authors - indexed by OpenAlexcited 39
- indexed by OpenAlexcited 38
Effective-Resistance-Reducing Flows, Spectrally Thin Trees, and Asymmetric TSP
2015 · Annual Symposium on Foundations of Computer Science · 2 authors - indexed by OpenAlexcited 34
A (Slightly) Improved Approximation Algorithm for Metric TSP
2023 · Operations Research · 3 authors