Shayan Oveis Gharan
According to our database1,
Shayan Oveis Gharan
authored at least 63 papers
between 2007 and 2024.
Collaborative distances:
Collaborative distances:
Timeline
Legend:
Book In proceedings Article PhD thesis Dataset OtherLinks
On csauthors.net:
Bibliography
2024
2023
Proceedings of the Integer Programming and Combinatorial Optimization, 2023
Proceedings of the 14th Innovations in Theoretical Computer Science Conference, 2023
Proceedings of the 38th Computational Complexity Conference, 2023
Proceedings of the Approximation, 2023
2022
CoRR, 2022
An improved approximation algorithm for the minimum <i>k</i>-edge connected multi-subgraph problem.
Proceedings of the STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20, 2022
Proceedings of the 13th Innovations in Theoretical Computer Science Conference, 2022
Proceedings of the 63rd IEEE Annual Symposium on Foundations of Computer Science, 2022
2021
An Improved Approximation Algorithm for the Minimum k-Edge Connected Multi-Subgraph Problem.
CoRR, 2021
Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021
Log-concave polynomials IV: approximate exchange, tight mixing times, and near-optimal sampling of forests.
Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021
A Matrix Trickle-Down Theorem on Simplicial Complexes and Applications to Sampling Colorings.
Proceedings of the 62nd IEEE Annual Symposium on Foundations of Computer Science, 2021
2020
Log-Concave Polynomials IV: Exchange Properties, Tight Mixing Times, and Faster Sampling of Spanning Trees.
CoRR, 2020
Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020
Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020
Spectral Independence in High-Dimensional Expanders and Applications to the Hardcore Model.
Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020
2019
Log-concave polynomials II: high-dimensional walks and an FPRAS for counting bases of a matroid.
Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019
A Polynomial Time MCMC Method for Sampling from Continuous Determinantal Point Processes.
Proceedings of the 36th International Conference on Machine Learning, 2019
Proceedings of the 36th International Conference on Machine Learning, 2019
2018
Time-Space Tradeoffs for Learning Finite Functions from Random Evaluations, with Applications to Polynomials.
Electron. Colloquium Comput. Complex., 2018
Log-Concave Polynomials III: Mason's Ultra-Log-Concavity Conjecture for Independent Sets of Matroids.
CoRR, 2018
Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018
Nash Social Welfare for Indivisible Items under Separable, Piecewise-Linear Concave Utilities.
Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018
Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018
Proceedings of the 9th Innovations in Theoretical Computer Science Conference, 2018
Log-Concave Polynomials, Entropy, and a Deterministic Approximation Algorithm for Counting Bases of Matroids.
Proceedings of the 59th IEEE Annual Symposium on Foundations of Computer Science, 2018
2017
An <i>O</i>(log <i>n</i>/log log <i>n</i>)-Approximation Algorithm for the Asymmetric Traveling Salesman Problem.
Oper. Res., 2017
Time-Space Tradeoffs for Learning from Small Test Spaces: Learning Low Degree Polynomial Functions.
Electron. Colloquium Comput. Complex., 2017
A generalization of permanent inequalities and applications in counting and optimization.
Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017
Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017
Proceedings of the 8th Innovations in Theoretical Computer Science Conference, 2017
Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science, 2017
2016
Monte Carlo Markov Chains Algorithms for Sampling Strongly Rayleigh Distributions and Determinantal Point Processes.
CoRR, 2016
Monte Carlo Markov Chain Algorithms for Sampling Strongly Rayleigh Distributions and Determinantal Point Processes.
Proceedings of the 29th Conference on Learning Theory, 2016
2015
A New Regularity Lemma and Faster Approximation Algorithms for Low Threshold Rank Graphs.
Theory Comput., 2015
Proceedings of the IEEE 56th Annual Symposium on Foundations of Computer Science, 2015
2014
The Kadison-Singer Problem for Strongly Rayleigh Measures and Applications to Asymmetric TSP.
CoRR, 2014
Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014
Proceedings of the ACM Conference on Economics and Computation, 2014
2013
CoRR, 2013
Improved Cheeger's inequality: analysis of spectral partitioning algorithms through higher order spectral gap.
Proceedings of the Symposium on Theory of Computing Conference, 2013
2012
Math. Oper. Res., 2012
Proceedings of the 44th Symposium on Theory of Computing Conference, 2012
Simultaneous approximations for adversarial and stochastic online budgeted allocation.
Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 2012
A Rounding by Sampling Approach to the Minimum Size k-Arc Connected Subgraph Problem.
Proceedings of the Automata, Languages, and Programming - 39th International Colloquium, 2012
Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science, 2012
2011
Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 2011
Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 2011
Proceedings of the IEEE 52nd Annual Symposium on Foundations of Computer Science, 2011
2010
An O(log n/ log log n)-approximation Algorithm for the Asymmetric Traveling Salesman Problem.
Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, 2010
2009
2008
Proceedings of the Second Asia International Conference on Modelling and Simulation, 2008
2007