Shayan Oveis Gharan

According to our database1, Shayan Oveis Gharan authored at least 63 papers between 2007 and 2024.

Collaborative distances:

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Dataset
Other 

Links

On csauthors.net:

Bibliography

2024
On approximability of the Permanent of PSD matrices.
CoRR, 2024

2023
Complete Log Concavity of Coverage-Like Functions.
CoRR, 2023

A Deterministic Better-than-3/2 Approximation Algorithm for Metric TSP.
Proceedings of the Integer Programming and Combinatorial Optimization, 2023

Matroid Partition Property and the Secretary Problem.
Proceedings of the 14th Innovations in Theoretical Computer Science Conference, 2023

An Improved Trickle down Theorem for Partite Complexes.
Proceedings of the 38th Computational Complexity Conference, 2023

On Optimization and Counting of Non-Broken Bases of Matroids.
Proceedings of the Approximation, 2023

2022
A (Slightly) Improved Deterministic Approximation Algorithm for Metric TSP.
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

Counting and Sampling Perfect Matchings in Regular Expanding Non-Bipartite Graphs.
Proceedings of the 13th Innovations in Theoretical Computer Science Conference, 2022

A (Slightly) Improved Bound on the Integrality Gap of the Subtour LP for TSP.
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

A (slightly) improved approximation algorithm for metric TSP.
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
On the Bias of Reed-Muller Codes over Odd Prime Fields.
SIAM J. Discret. Math., 2020

Log-Concave Polynomials IV: Exchange Properties, Tight Mixing Times, and Faster Sampling of Spanning Trees.
CoRR, 2020

An improved approximation algorithm for TSP in the half integral case.
Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020

Composable Core-sets for Determinant Maximization Problems via Spectral Spanners.
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

Composable Core-sets for Determinant Maximization: A Simple Near-Optimal Algorithm.
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

A Polynomial Time MCMC Method for Sampling from Continuous DPPs.
CoRR, 2018

A simply exponential upper bound on the maximum number of stable matchings.
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

Approximating the Largest Root and Applications to Interlacing Families.
Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

Graph Clustering using Effective Resistance.
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

Approximation Algorithms for Finding Maximum Induced Expanders.
Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

Nash Social Welfare, Matrix Permanent, and Stable Polynomials.
Proceedings of the 8th Innovations in Theoretical Computer Science Conference, 2017

Simply Exponential Approximation of the Permanent of Positive Semidefinite Matrices.
Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science, 2017

2016
Almost Optimal Local Graph Clustering Using Evolving Sets.
J. ACM, 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

Effective-Resistance-Reducing Flows, Spectrally Thin Trees, and Asymmetric TSP.
Proceedings of the IEEE 56th Annual Symposium on Foundations of Computer Science, 2015

2014
Multiway Spectral Partitioning and Higher-Order Cheeger Inequalities.
J. ACM, 2014

The Kadison-Singer Problem for Strongly Rayleigh Measures and Applications to Asymmetric TSP.
CoRR, 2014

Effective-Resistance-Reducing Flows and Asymmetric TSP.
CoRR, 2014

Partitioning into Expanders.
Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

Dynamic matching market design.
Proceedings of the ACM Conference on Economics and Computation, 2014

2013
Improved ARV Rounding in Small-set Expanders and Graphs of Bounded Threshold Rank
CoRR, 2013

On Variants of the Matroid Secretary Problem.
Algorithmica, 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
Online Stochastic Matching: Online Actions Based on Offline Statistics.
Math. Oper. Res., 2012

A Universal upper bound on Graph Diameter based on Laplacian Eigenvalues
CoRR, 2012

Sharp Bounds on Random Walk Eigenvalues via Spectral Embedding
CoRR, 2012

Multi-way spectral partitioning and higher-order cheeger inequalities.
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

Approximating the Expansion Profile and Almost Optimal Local Graph Clustering.
Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science, 2012

2011
Submodular Maximization by Simulated Annealing.
Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 2011

The Asymmetric Traveling Salesman Problem on Graphs with Bounded Genus.
Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 2011

A Randomized Rounding Approach to the Traveling Salesman Problem.
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
Minimizing movement.
ACM Trans. Algorithms, 2009

2008
A Time Warping Speech Recognition System Based on Particle Swarm Optimization.
Proceedings of the Second Asia International Conference on Modelling and Simulation, 2008

2007
Spanning trees with minimum weighted degrees.
Inf. Process. Lett., 2007


  Loading...