vix.ing · top · new · best · stats · spec

Gharan, Shayan Oveis

  1. Log-Concave Polynomials II: High-Dimensional Walks and an FPRAS for Counting Bases of a Matroid
    2018/11/05 by Nima Anari, Anari, Nima, Kuikui Liu +5 · 10 citations
    Computer Science · Mathematics · #Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Geometry and complex manifolds #Markov Chains and Monte Carlo Methods #Probability (math.PR) #Spectral Theory (math.SP) #Topological and Geometric Data Analysis
  2. A (Slightly) Improved Approximation Algorithm for Metric TSP
    2020/07/02 by Karlin, Anna R., Klein, Nathan, Gharan, Shayan Oveis · 9 citations
    #Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Probability (math.PR)
  3. Graph Clustering using Effective Resistance
    2017/11/17 by Alev, Vedat Levi, Anari, Nima, Lau, Lap Chi +1 · 5 citations
    #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
  4. Spectral Independence in High-Dimensional Expanders and Applications to\n the Hardcore Model
    2020/01/01 by Nima Anari, Kuikui Liu, Anari, Nima +3 · 6 citations
    Mathematics · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Markov Chains and Monte Carlo Methods #Random Matrices and Applications #Stochastic processes and statistical mechanics
  5. Log-Concave Polynomials I: Entropy and a Deterministic Approximation Algorithm for Counting Bases of Matroids
    2018/07/02 by Anari, Nima, Gharan, Shayan Oveis, Vinzant, Cynthia · 5 citations
    #Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Information Theory (cs.IT) #Probability (math.PR)
  6. Log-Concave Polynomials III: Mason's Ultra-Log-Concavity Conjecture for Independent Sets of Matroids
    2018/11/05 by Anari, Nima, Liu, Kuikui, Gharan, Shayan Oveis +1 · 4 citations
    #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Probability (math.PR)
  7. Online Stochastic Matching: Online Actions Based on Offline Statistics
    2010/07/09 by Manshadi, Vahideh H., Gharan, Shayan Oveis, Saberi, Amin · 3 citations
    #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
  8. A Matrix Trickle-Down Theorem on Simplicial Complexes and Applications to Sampling Colorings
    2021/06/07 by Dorna Abdolazimi, Kuikui Liu, Abdolazimi, Dorna +3 · 4 citations
    Computer Science · Mathematics · #Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Markov Chains and Monte Carlo Methods #Probability (math.PR) #Random Matrices and Applications #Topological and Geometric Data Analysis
  9. Submodular Maximization by Simulated Annealing
    2010/07/09 by Shayan Oveis Gharan, Gharan, Shayan Oveis, Jan Vondrák +1 · 2 citations
    Computer Science · #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
  10. Multi-way spectral partitioning and higher-order Cheeger inequalities
    2011/11/04 by Lee, James R., Gharan, Shayan Oveis, Trevisan, Luca · 2 citations
    #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Metric Geometry (math.MG) #Spectral Theory (math.SP)
  11. Monte Carlo Markov Chain Algorithms for Sampling Strongly Rayleigh\n Distributions and Determinantal Point Processes
    2016/02/16 by Nima Anari, Anari, Nima, Shayan Oveis Gharan +3 · 2 citations
    Computer Science · Mathematics · #Bayesian Methods and Mixture Models #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Markov Chains and Monte Carlo Methods #Point processes and geometric inequalities #Probability (math.PR)
  12. Nash Social Welfare, Matrix Permanent, and Stable Polynomials
    2016/09/22 by Anari, Nima, Gharan, Shayan Oveis, Saberi, Amin +1 · 2 citations
    #Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
  13. Nash Social Welfare for Indivisible Items under Separable,\n Piecewise-Linear Concave Utilities
    2016/12/15 by Nima Anari, Anari, Nima, Tung Mai +5 · 2 citations
    Decision Sciences · Economics, Econometrics and Finance · #Combinatorics (math.CO) #Computer Science and Game Theory (cs.GT) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #Economic theories and models #FOS: Computer and information sciences #FOS: Mathematics #Game Theory and Applications #Game Theory and Voting Systems
  14. Composable Core-sets for Determinant Maximization Problems via Spectral Spanners
    2018/07/31 by Indyk, Piotr, Mahabadi, Sepideh, Gharan, Shayan Oveis +1 · 2 citations
    #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML)
  15. Composable Core-sets for Determinant Maximization: A Simple Near-Optimal Algorithm
    2019/07/06 by Indyk, Piotr, Mahabadi, Sepideh, Gharan, Shayan Oveis +1 · 2 citations
    #Data Structures and Algorithms (cs.DS) #F.2.0 #FOS: Computer and information sciences #G.1.2 #G.1.6 #G.2.2 #Machine Learning (cs.LG)
  16. Matroid Partition Property and the Secretary Problem
    2021/11/24 by Abdolazimi, Dorna, Karlin, Anna R., Klein, Nathan +1 · 2 citations
    #Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
  17. The Asymmetric Traveling Salesman Problem on Graphs with Bounded Genus
    2009/09/15 by Gharan, Shayan Oveis, Saberi, Amin · 1 citation
    #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences
  18. A Rounding by Sampling Approach to the Minimum Size k-Arc Connected Subgraph Problem
    2012/05/07 by Laekhanukit, Bundit, Gharan, Shayan Oveis, Singh, Mohit · 1 citation
    #Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics
  19. Approximating the Expansion Profile and Almost Optimal Local Graph\n Clustering
    2012/04/09 by Shayan Oveis Gharan, Luca Trevisan, Gharan, Shayan Oveis +1 · 1 citation
    Computer Science · Engineering · Mathematics · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Graph theory and applications #VLSI and FPGA Design Techniques
  20. A Universal upper bound on Graph Diameter based on Laplacian Eigenvalues
    2012/12/12 by Shayan Oveis Gharan, Luca Trevisan, Gharan, Shayan Oveis +1 · 1 citation
    Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory #Probability (math.PR)
  21. Improved Cheeger's Inequality: Analysis of Spectral Partitioning Algorithms through Higher Order Spectral Gap
    2013/01/23 by Kwok, Tsz Chiu, Lau, Lap Chi, Lee, Yin Tat +2 · 1 citation
    #Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (stat.ML) #Spectral Theory (math.SP)
  22. The Kadison-Singer Problem for Strongly Rayleigh Measures and Applications to Asymmetric TSP
    2014/12/03 by Anari, Nima, Gharan, Shayan Oveis · 1 citation
    #Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Probability (math.PR)
  23. Approximating the Largest Root and Applications to Interlacing Families
    2017/04/12 by Anari, Nima, Gharan, Shayan Oveis, Saberi, Amin +1 · 1 citation
    #Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics
  24. Simply Exponential Approximation of the Permanent of Positive Semidefinite Matrices
    2017/04/11 by Anari, Nima, Gurvits, Leonid, Gharan, Shayan Oveis +1 · 1 citation
    #Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #FOS: Physical sciences #Probability (math.PR) #Quantum Physics (quant-ph)
  25. On the Bias of Reed-Muller Codes over Odd Prime Fields
    2018/06/18 by Beame, Paul, Gharan, Shayan Oveis, Yang, Xin · 1 citation
    #Computational Complexity (cs.CC) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Information Theory (cs.IT)
  26. An Improved Approximation Algorithm for TSP in the Half Integral Case
    2019/08/01 by Karlin, Anna, Klein, Nathan, Gharan, Shayan Oveis · 1 citation
    #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Probability (math.PR)
  27. A (Slightly) Improved Bound on the Integrality Gap of the Subtour LP for TSP
    2021/05/20 by Karlin, Anna, Klein, Nathan, Gharan, Shayan Oveis · 1 citation
    #Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Probability (math.PR)
  28. On approximability of the Permanent of PSD matrices
    2024/04/16 by Farzam Ebrahimnejad, Ansh Nagda, Ebrahimnejad, Farzam +3 · 1 citation
    Computer Science · Mathematics · Physics and Astronomy · #Advanced Mathematical Theories and Applications #Advanced Optimization Algorithms Research #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Matrix Theory and Algorithms
  29. An Improved Trickle-Down Theorem for Partite Complexes
    2022/08/09 by Dorna Abdolazimi, Abdolazimi, Dorna, Shayan Oveis Gharan +1 · 1 citation
    Computer Science · Mathematics · #Advanced Combinatorial Mathematics #Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Markov Chains and Monte Carlo Methods #Topological and Geometric Data Analysis
  30. Unweighted One-Sided Code Sparsifiers and Thin Subgraphs
    2025/02/05 by Gharan, Shayan Oveis, Sahami, Arvin · 1 citation
    #Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics