default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDShayan Oveis Gharan
Person information
Refine list
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
showing all ?? records
2020 – today
- 2024
[i49]Farzam Ebrahimnejad, Ansh Nagda, Shayan Oveis Gharan:
On approximability of the Permanent of PSD matrices. CoRR abs/2404.10959 (2024)- 2023
- [c44]Dorna Abdolazimi, Kasper Lindberg, Shayan Oveis Gharan:
On Optimization and Counting of Non-Broken Bases of Matroids. APPROX/RANDOM 2023: 40:1-40:14 - [c43]Dorna Abdolazimi, Shayan Oveis Gharan:
An Improved Trickle down Theorem for Partite Complexes. CCC 2023: 10:1-10:16 - [c42]Dorna Abdolazimi, Anna R. Karlin, Nathan Klein, Shayan Oveis Gharan:
Matroid Partition Property and the Secretary Problem. ITCS 2023: 2:1-2:9 - [c41]Anna R. Karlin, Nathan Klein
, Shayan Oveis Gharan:
A Deterministic Better-than-3/2 Approximation Algorithm for Metric TSP. IPCO 2023: 261-274 - [i48]Dorna Abdolazimi, Shayan Oveis Gharan:
Complete Log Concavity of Coverage-Like Functions. CoRR abs/2303.03741 (2023) - [i47]Dorna Abdolazimi, Kasper Lindberg, Shayan Oveis Gharan:
On Optimization and Counting of Non-Broken Bases of Matroids. CoRR abs/2305.03307 (2023) - 2022
- [c40]Anna R. Karlin, Nathan Klein, Shayan Oveis Gharan:
A (Slightly) Improved Bound on the Integrality Gap of the Subtour LP for TSP. FOCS 2022: 832-843 - [c39]Farzam Ebrahimnejad, Ansh Nagda, Shayan Oveis Gharan:
Counting and Sampling Perfect Matchings in Regular Expanding Non-Bipartite Graphs. ITCS 2022: 61:1-61:12 - [c38]Anna R. Karlin, Nathan Klein, Shayan Oveis Gharan, Xinzhi Zhang:
An improved approximation algorithm for the minimum k-edge connected multi-subgraph problem. STOC 2022: 1612-1620 - [i46]Dorna Abdolazimi, Shayan Oveis Gharan:
An Improved Trickle-Down Theorem for Partite Complexes. CoRR abs/2208.04486 (2022) - [i45]Anna R. Karlin, Nathan Klein, Shayan Oveis Gharan:
A (Slightly) Improved Deterministic Approximation Algorithm for Metric TSP. CoRR abs/2212.06296 (2022) - 2021
- [c37]Dorna Abdolazimi, Kuikui Liu, Shayan Oveis Gharan:
A Matrix Trickle-Down Theorem on Simplicial Complexes and Applications to Sampling Colorings. FOCS 2021: 161-172 - [c36]Anna R. Karlin, Nathan Klein, Shayan Oveis Gharan:
A (slightly) improved approximation algorithm for metric TSP. STOC 2021: 32-45 - [c35]Nima Anari, Kuikui Liu, Shayan Oveis Gharan, Cynthia Vinzant, Thuy-Duong Vuong:
Log-concave polynomials IV: approximate exchange, tight mixing times, and near-optimal sampling of forests. STOC 2021: 408-420 - [i44]Anna R. Karlin, Nathan Klein, Shayan Oveis Gharan, Xinzhi Zhang:
An Improved Approximation Algorithm for the Minimum k-Edge Connected Multi-Subgraph Problem. CoRR abs/2101.05921 (2021) - [i43]Farzam Ebrahimnejad, Ansh Nagda, Shayan Oveis Gharan:
Counting and Sampling Perfect Matchings in Regular Expanding Non-Bipartite Graphs. CoRR abs/2103.08683 (2021) - [i42]Anna R. Karlin, Nathan Klein, Shayan Oveis Gharan:
A (Slightly) Improved Bound on the Integrality Gap of the Subtour LP for TSP. CoRR abs/2105.10043 (2021) - [i41]Dorna Abdolazimi, Kuikui Liu, Shayan Oveis Gharan:
A Matrix Trickle-Down Theorem on Simplicial Complexes and Applications to Sampling Colorings. CoRR abs/2106.03845 (2021) - [i40]Dorna Abdolazimi, Anna R. Karlin, Nathan Klein, Shayan Oveis Gharan:
Matroid Partition Property and the Secretary Problem. CoRR abs/2111.12436 (2021) - 2020
- [j9]Paul Beame, Shayan Oveis Gharan, Xin Yang:
On the Bias of Reed-Muller Codes over Odd Prime Fields. SIAM J. Discret. Math. 34(2): 1232-1247 (2020) - [c34]Nima Anari, Kuikui Liu, Shayan Oveis Gharan:
Spectral Independence in High-Dimensional Expanders and Applications to the Hardcore Model. FOCS 2020: 1319-1330 - [c33]Piotr Indyk, Sepideh Mahabadi, Shayan Oveis Gharan, Alireza Rezaei:
Composable Core-sets for Determinant Maximization Problems via Spectral Spanners. SODA 2020: 1675-1694 - [c32]Anna R. Karlin, Nathan Klein, Shayan Oveis Gharan:
An improved approximation algorithm for TSP in the half integral case. STOC 2020: 28-39 - [i39]Nima Anari, Kuikui Liu, Shayan Oveis Gharan:
Spectral Independence in High-Dimensional Expanders and Applications to the Hardcore Model. CoRR abs/2001.00303 (2020) - [i38]Nima Anari, Kuikui Liu, Shayan Oveis Gharan, Cynthia Vinzant:
Log-Concave Polynomials IV: Exchange Properties, Tight Mixing Times, and Faster Sampling of Spanning Trees. CoRR abs/2004.07220 (2020) - [i37]Anna R. Karlin, Nathan Klein, Shayan Oveis Gharan:
A (Slightly) Improved Approximation Algorithm for Metric TSP. CoRR abs/2007.01409 (2020)
2010 – 2019
- 2019
- [c31]Sepideh Mahabadi, Piotr Indyk, Shayan Oveis Gharan, Alireza Rezaei:
Composable Core-sets for Determinant Maximization: A Simple Near-Optimal Algorithm. ICML 2019: 4254-4263 - [c30]Alireza Rezaei, Shayan Oveis Gharan:
A Polynomial Time MCMC Method for Sampling from Continuous Determinantal Point Processes. ICML 2019: 5438-5447 - [c29]Nima Anari, Kuikui Liu, Shayan Oveis Gharan, Cynthia Vinzant:
Log-concave polynomials II: high-dimensional walks and an FPRAS for counting bases of a matroid. STOC 2019: 1-12 - [i36]Piotr Indyk, Sepideh Mahabadi, Shayan Oveis Gharan, Alireza Rezaei:
Composable Core-sets for Determinant Maximization: A Simple Near-Optimal Algorithm. CoRR abs/1907.03197 (2019) - [i35]Anna R. Karlin, Nathan Klein, Shayan Oveis Gharan:
An Improved Approximation Algorithm for TSP in the Half Integral Case. CoRR abs/1908.00227 (2019) - 2018
- [c28]Paul Beame, Shayan Oveis Gharan, Xin Yang:
Time-Space Tradeoffs for Learning Finite Functions from Random Evaluations, with Applications to Polynomials. COLT 2018: 843-856 - [c27]Nima Anari, Shayan Oveis Gharan, Cynthia Vinzant:
Log-Concave Polynomials, Entropy, and a Deterministic Approximation Algorithm for Counting Bases of Matroids. FOCS 2018: 35-46 - [c26]Vedat Levi Alev, Nima Anari, Lap Chi Lau, Shayan Oveis Gharan:
Graph Clustering using Effective Resistance. ITCS 2018: 41:1-41:16 - [c25]Nima Anari, Shayan Oveis Gharan, Amin Saberi, Nikhil Srivastava:
Approximating the Largest Root and Applications to Interlacing Families. SODA 2018: 1015-1028 - [c24]Nima Anari, Tung Mai, Shayan Oveis Gharan, Vijay V. Vazirani:
Nash Social Welfare for Indivisible Items under Separable, Piecewise-Linear Concave Utilities. SODA 2018: 2274-2290 - [c23]Anna R. Karlin, Shayan Oveis Gharan, Robbie Weber:
A simply exponential upper bound on the maximum number of stable matchings. STOC 2018: 920-925 - [i34]Paul Beame, Shayan Oveis Gharan, Xin Yang:
On the Bias of Reed-Muller Codes over Odd Prime Fields. CoRR abs/1806.06973 (2018) - [i33]Nima Anari, Shayan Oveis Gharan, Cynthia Vinzant:
Log-concave polynomials, entropy, and a deterministic approximation algorithm for counting bases of matroids. CoRR abs/1807.00929 (2018) - [i32]Piotr Indyk, Sepideh Mahabadi, Shayan Oveis Gharan, Alireza Rezaei:
Composable Core-sets for Determinant Maximization Problems via Spectral Spanners. CoRR abs/1807.11648 (2018) - [i31]Shayan Oveis Gharan, Alireza Rezaei:
A Polynomial Time MCMC Method for Sampling from Continuous DPPs. CoRR abs/1810.08867 (2018) - [i30]Nima Anari, Kuikui Liu, Shayan Oveis Gharan, Cynthia Vinzant:
Log-Concave Polynomials III: Mason's Ultra-Log-Concavity Conjecture for Independent Sets of Matroids. CoRR abs/1811.01600 (2018) - [i29]Nima Anari, Kuikui Liu, Shayan Oveis Gharan, Cynthia Vinzant:
Log-Concave Polynomials II: High-Dimensional Walks and an FPRAS for Counting Bases of a Matroid. CoRR abs/1811.01816 (2018) - [i28]Paul Beame, Shayan Oveis Gharan, Xin Yang:
Time-Space Tradeoffs for Learning Finite Functions from Random Evaluations, with Applications to Polynomials. Electron. Colloquium Comput. Complex. TR18 (2018) - 2017
- [j8]Arash Asadpour, Michel X. Goemans, Aleksander Madry, Shayan Oveis Gharan, Amin Saberi:
An O(log n/log log n)-Approximation Algorithm for the Asymmetric Traveling Salesman Problem. Oper. Res. 65(4): 1043-1061 (2017) - [c22]Nima Anari, Leonid Gurvits, Shayan Oveis Gharan, Amin Saberi:
Simply Exponential Approximation of the Permanent of Positive Semidefinite Matrices. FOCS 2017: 914-925 - [c21]Nima Anari, Shayan Oveis Gharan, Amin Saberi, Mohit Singh:
Nash Social Welfare, Matrix Permanent, and Stable Polynomials. ITCS 2017: 36:1-36:12 - [c20]Shayan Oveis Gharan, Alireza Rezaei:
Approximation Algorithms for Finding Maximum Induced Expanders. SODA 2017: 1158-1169 - [c19]Nima Anari, Shayan Oveis Gharan:
A generalization of permanent inequalities and applications in counting and optimization. STOC 2017: 384-396 - [i27]Nima Anari, Shayan Oveis Gharan:
A Generalization of Permanent Inequalities and Applications in Counting and Optimization. CoRR abs/1702.02937 (2017) - [i26]Nima Anari, Leonid Gurvits, Shayan Oveis Gharan, Amin Saberi:
Simply Exponential Approximation of the Permanent of Positive Semidefinite Matrices. CoRR abs/1704.03486 (2017) - [i25]Nima Anari, Shayan Oveis Gharan, Amin Saberi, Nikhil Srivastava:
Approximating the Largest Root and Applications to Interlacing Families. CoRR abs/1704.03892 (2017) - [i24]Paul Beame, Shayan Oveis Gharan, Xin Yang:
Time-Space Tradeoffs for Learning from Small Test Spaces: Learning Low Degree Polynomial Functions. CoRR abs/1708.02640 (2017) - [i23]Anna R. Karlin, Shayan Oveis Gharan, Robbie Weber:
A Simply Exponential Upper Bound on the Maximum Number of Stable Matchings. CoRR abs/1711.01032 (2017) - [i22]Vedat Levi Alev, Nima Anari, Lap Chi Lau, Shayan Oveis Gharan:
Graph Clustering using Effective Resistance. CoRR abs/1711.06530 (2017) - [i21]Paul Beame, Shayan Oveis Gharan, Xin Yang:
Time-Space Tradeoffs for Learning from Small Test Spaces: Learning Low Degree Polynomial Functions. Electron. Colloquium Comput. Complex. TR17 (2017) - 2016
- [j7]Reid Andersen, Shayan Oveis Gharan, Yuval Peres, Luca Trevisan:
Almost Optimal Local Graph Clustering Using Evolving Sets. J. ACM 63(2): 15:1-15:31 (2016) - [c18]Nima Anari, Shayan Oveis Gharan, Alireza Rezaei:
Monte Carlo Markov Chain Algorithms for Sampling Strongly Rayleigh Distributions and Determinantal Point Processes. COLT 2016: 103-115 - [i20]Nima Anari, Shayan Oveis Gharan, Alireza Rezaei:
Monte Carlo Markov Chains Algorithms for Sampling Strongly Rayleigh Distributions and Determinantal Point Processes. CoRR abs/1602.05242 (2016) - [i19]Nima Anari, Shayan Oveis Gharan, Amin Saberi, Mohit Singh:
Nash Social Welfare, Matrix Permanent, and Stable Polynomials. CoRR abs/1609.07056 (2016) - [i18]Nima Anari, Tung Mai, Shayan Oveis Gharan, Vijay V. Vazirani:
Nash Social Welfare for Indivisible Items under Separable, Piecewise-Linear Concave Utilities. CoRR abs/1612.05191 (2016) - 2015
- [j6]Shayan Oveis Gharan, Luca Trevisan:
A New Regularity Lemma and Faster Approximation Algorithms for Low Threshold Rank Graphs. Theory Comput. 11: 241-256 (2015) - [c17]Nima Anari, Shayan Oveis Gharan:
Effective-Resistance-Reducing Flows, Spectrally Thin Trees, and Asymmetric TSP. FOCS 2015: 20-39 - [i17]Shayan Oveis Gharan, Alireza Rezaei:
Approximation Algorithms for Finding Maximum Induced Expanders. CoRR abs/1511.02786 (2015) - 2014
- [j5]James R. Lee, Shayan Oveis Gharan, Luca Trevisan:
Multiway Spectral Partitioning and Higher-Order Cheeger Inequalities. J. ACM 61(6): 37:1-37:30 (2014) - [c16]Mohammad Akbarpour, Shengwu Li, Shayan Oveis Gharan:
Dynamic matching market design. EC 2014: 355 - [c15]Shayan Oveis Gharan, Luca Trevisan:
Partitioning into Expanders. SODA 2014: 1256-1266 - [i16]Mohammad Akbarpour, Shengwu Li, Shayan Oveis Gharan:
Dynamic Matching Market Design. CoRR abs/1402.3643 (2014) - [i15]Nima Anari, Shayan Oveis Gharan:
Effective-Resistance-Reducing Flows and Asymmetric TSP. CoRR abs/1411.4613 (2014) - [i14]Nima Anari, Shayan Oveis Gharan:
The Kadison-Singer Problem for Strongly Rayleigh Measures and Applications to Asymmetric TSP. CoRR abs/1412.1143 (2014) - 2013
- [j4]Shayan Oveis Gharan, Jan Vondrák:
On Variants of the Matroid Secretary Problem. Algorithmica 67(4): 472-497 (2013) - [c14]Shayan Oveis Gharan, Luca Trevisan:
A New Regularity Lemma and Faster Approximation Algorithms for Low Threshold Rank Graphs. APPROX-RANDOM 2013: 303-316 - [c13]Tsz Chiu Kwok, Lap Chi Lau, Yin Tat Lee, Shayan Oveis Gharan, Luca Trevisan:
Improved Cheeger's inequality: analysis of spectral partitioning algorithms through higher order spectral gap. STOC 2013: 11-20 - [i13]Tsz Chiu Kwok, Lap Chi Lau, Yin Tat Lee, Shayan Oveis Gharan, Luca Trevisan:
Improved Cheeger's Inequality: Analysis of Spectral Partitioning Algorithms through Higher Order Spectral Gap. CoRR abs/1301.5584 (2013) - [i12]Shayan Oveis Gharan, Luca Trevisan:
Improved ARV Rounding in Small-set Expanders and Graphs of Bounded Threshold Rank. CoRR abs/1304.2060 (2013) - [i11]Shayan Oveis Gharan, Luca Trevisan:
Partitioning into Expanders. CoRR abs/1309.3223 (2013) - 2012
- [j3]Vahideh H. Manshadi, Shayan Oveis Gharan, Amin Saberi:
Online Stochastic Matching: Online Actions Based on Offline Statistics. Math. Oper. Res. 37(4): 559-573 (2012) - [c12]Shayan Oveis Gharan, Luca Trevisan:
Approximating the Expansion Profile and Almost Optimal Local Graph Clustering. FOCS 2012: 187-196 - [c11]Bundit Laekhanukit, Shayan Oveis Gharan, Mohit Singh:
A Rounding by Sampling Approach to the Minimum Size k-Arc Connected Subgraph Problem. ICALP (1) 2012: 606-616 - [c10]Vahab S. Mirrokni, Shayan Oveis Gharan, Morteza Zadimoghaddam:
Simultaneous approximations for adversarial and stochastic online budgeted allocation. SODA 2012: 1690-1701 - [c9]James R. Lee, Shayan Oveis Gharan, Luca Trevisan:
Multi-way spectral partitioning and higher-order cheeger inequalities. STOC 2012: 1117-1130 - [i10]Shayan Oveis Gharan, Luca Trevisan:
Approximating the Expansion Profile and Almost Optimal Local Graph Clustering. CoRR abs/1204.2021 (2012) - [i9]Bundit Laekhanukit, Shayan Oveis Gharan, Mohit Singh:
A Rounding by Sampling Approach to the Minimum Size k-Arc Connected Subgraph Problem. CoRR abs/1205.1262 (2012) - [i8]Russell Lyons, Shayan Oveis Gharan:
Sharp Bounds on Random Walk Eigenvalues via Spectral Embedding. CoRR abs/1211.0589 (2012) - [i7]Shayan Oveis Gharan, Luca Trevisan:
A New Regularity Lemma and Faster Approximation Algorithms for Low Threshold Rank Graphs. CoRR abs/1212.1831 (2012) - [i6]Shayan Oveis Gharan, Luca Trevisan:
A Universal upper bound on Graph Diameter based on Laplacian Eigenvalues. CoRR abs/1212.2701 (2012) - 2011
- [c8]Shayan Oveis Gharan, Jan Vondrák:
On Variants of the Matroid Secretary Problem. ESA 2011: 335-346 - [c7]Shayan Oveis Gharan, Amin Saberi, Mohit Singh:
A Randomized Rounding Approach to the Traveling Salesman Problem. FOCS 2011: 550-559 - [c6]Shayan Oveis Gharan, Amin Saberi:
The Asymmetric Traveling Salesman Problem on Graphs with Bounded Genus. SODA 2011: 967-975 - [c5]Shayan Oveis Gharan, Jan Vondrák:
Submodular Maximization by Simulated Annealing. SODA 2011: 1098-1116 - [c4]Vahideh H. Manshadi, Shayan Oveis Gharan, Amin Saberi:
Online Stochastic Matching: Online Actions Based on Offline Statistics. SODA 2011: 1285-1294 - [i5]Shayan Oveis Gharan, Jan Vondrák:
On Variants of the Matroid Secretary Problem. CoRR abs/1104.4081 (2011) - [i4]James R. Lee, Shayan Oveis Gharan, Luca Trevisan:
Multi-way spectral partitioning and higher-order Cheeger inequalities. CoRR abs/1111.1055 (2011) - 2010
- [c3]Arash Asadpour, Michel X. Goemans, Aleksander Madry, Shayan Oveis Gharan, Amin Saberi:
An O(log n/ log log n)-approximation Algorithm for the Asymmetric Traveling Salesman Problem. SODA 2010: 379-389 - [i3]Shayan Oveis Gharan, Jan Vondrák:
Submodular Maximization by Simulated Annealing. CoRR abs/1007.1632 (2010) - [i2]Vahideh H. Manshadi, Shayan Oveis Gharan, Amin Saberi:
Online Stochastic Matching: Online Actions Based on Offline Statistics. CoRR abs/1007.1673 (2010)
2000 – 2009
- 2009
- [j2]Erik D. Demaine, Mohammad Taghi Hajiaghayi, Hamid Mahini, Amin S. Sayedi-Roshkhar, Shayan Oveis Gharan, Morteza Zadimoghaddam:
Minimizing movement. ACM Trans. Algorithms 5(3): 30:1-30:30 (2009) - [i1]Shayan Oveis Gharan, Amin Saberi:
Asymmetric Traveling Salesman Problem on Graphs with Bounded Genus. CoRR abs/0909.2849 (2009) - 2008
- [c2]Saeed Rategh, Farbod Razzazi, Amir Masoud Rahmani, Shayan Oveis Gharan:
A Time Warping Speech Recognition System Based on Particle Swarm Optimization. Asia International Conference on Modelling and Simulation 2008: 585-590 - 2007
- [j1]Mohammad Ghodsi, Hamid Mahini, Kian Mirjalali, Shayan Oveis Gharan, Amin S. Sayedi-Roshkhar, Morteza Zadimoghaddam:
Spanning trees with minimum weighted degrees. Inf. Process. Lett. 104(3): 113-116 (2007) - [c1]Erik D. Demaine, Mohammad Taghi Hajiaghayi, Hamid Mahini, Amin S. Sayedi-Roshkhar, Shayan Oveis Gharan, Morteza Zadimoghaddam:
Minimizing movement. SODA 2007: 258-267
Coauthor Index
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
Unpaywalled article links
Add open access links from 
to the list of external document links (if available).
Privacy notice: By enabling the option above, your browser will contact the API of unpaywall.org to load hyperlinks to open access articles. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Unpaywall privacy policy.
Archived links via Wayback Machine
For web page which are no longer available, try to retrieve content from the 
of the Internet Archive (if available).
Privacy notice: By enabling the option above, your browser will contact the API of archive.org to check for archived content of web pages that are no longer available. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Internet Archive privacy policy.
Reference lists
Add a list of references from 
, 
, and 
to record detail pages.
load references from crossref.org and opencitations.net
Privacy notice: By enabling the option above, your browser will contact the APIs of crossref.org, opencitations.net, and semanticscholar.org to load article reference information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Crossref privacy policy and the OpenCitations privacy policy, as well as the AI2 Privacy Policy covering Semantic Scholar.
Citation data
Add a list of citing articles from and to record detail pages.
load citations from opencitations.net
Privacy notice: By enabling the option above, your browser will contact the API of opencitations.net and semanticscholar.org to load citation information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the OpenCitations privacy policy as well as the AI2 Privacy Policy covering Semantic Scholar.
OpenAlex data
Load additional information about publications from 
.
Privacy notice: By enabling the option above, your browser will contact the API of openalex.org to load additional information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the information given by OpenAlex.
last updated on 2024-10-07 21:24 CEST by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by:
