Santosh S. Vempala

ORCID

Publication Activity (10 Years)

Years Active: 1993-2024
Publications (10 Years): 120

Top Venues

Publications

Yunbum Kook, Santosh S. Vempala, Matthew Shunshi Zhang
In-and-Out: Algorithmic Diffusion for Sampling Convex Bodies. CoRR (2024)
Max Dabagia, Christos H. Papadimitriou, Santosh S. Vempala
Computation with Sequences of Assemblies in a Model of the Brain. ALT (2024)
Richard Peng, Santosh S. Vempala
Solving Sparse Linear Systems Faster than Matrix Multiplication. Commun. ACM 67 (7) (2024)
Yunbum Kook, Santosh S. Vempala
Gaussian Cooling and Dikin Walks: The Interior-Point Method for Logconcave Sampling. COLT (2024)
Adam Tauman Kalai, Santosh S. Vempala
Calibrated Language Models Must Hallucinate. STOC (2024)
Khashayar Gatmiry, Jonathan A. Kelner, Santosh S. Vempala
Sampling Polytopes with Riemannian HMC: Faster Mixing via the Lewis Weights Barrier. COLT (2024)
Mirabel Reid, Santosh S. Vempala
Does GPT Really Get It? A Hierarchical Scale to Quantify Human vs AI's Understanding of Algorithms. CoRR (2024)
Max Dabagia, Daniel Mitropolsky, Christos H. Papadimitriou, Santosh S. Vempala
Coin-Flipping In The Brain: Statistical Learning with Neuronal Assemblies. CoRR (2024)
Adam Tauman Kalai, Santosh S. Vempala
Calibrated Language Models Must Hallucinate. CoRR (2023)
Mehrdad Ghadiri, Richard Peng, Santosh S. Vempala
The Bit Complexity of Efficient Continuous Optimization. CoRR (2023)
Xinyuan Cao, Santosh S. Vempala
Contrastive Moments: Unsupervised Halfspace Learning in Polynomial Time. CoRR (2023)
Xinyuan Cao, Santosh S. Vempala
Contrastive Moments: Unsupervised Halfspace Learning in Polynomial Time. NeurIPS (2023)
Yunbum Kook, Santosh S. Vempala
Efficiently Sampling the PSD Cone with the Metric Dikin Walk. CoRR (2023)
Pravesh Kothari, Santosh S. Vempala, Alexander S. Wein, Jeff Xu
Is Planted Coloring Easier than Planted Clique? COLT (2023)
Aditi Laddha, Santosh S. Vempala
Convergence of Gibbs Sampling: Coordinate Hit-and-Run Mixes Fast. Discret. Comput. Geom. 70 (2) (2023)
Yunbum Kook, Yin Tat Lee, Ruoqi Shen, Santosh S. Vempala
Condition-number-independent Convergence Rate of Riemannian Hamiltonian Monte Carlo with Numerical Integrators. COLT (2023)
Khashayar Gatmiry, Jonathan A. Kelner, Santosh S. Vempala
Sampling with Barriers: Faster Mixing via Lewis Weights. CoRR (2023)
He Jia, Pravesh Kothari, Santosh S. Vempala
Beyond Moments: Robustly Learning Affine Transformations with Asymptotically Optimal Error. CoRR (2023)
Pravesh K. Kothari, Santosh S. Vempala, Alexander S. Wein, Jeff Xu
Is Planted Coloring Easier than Planted Clique? CoRR (2023)
He Jia, Pravesh K. Kothari, Santosh S. Vempala
Beyond Moments: Robustly Learning Affine Transformations with Asymptotically Optimal Error. FOCS (2023)
Mehrdad Ghadiri, Richard Peng, Santosh S. Vempala
The Bit Complexity of Efficient Continuous Optimization. FOCS (2023)
Max Dabagia, Christos H. Papadimitriou, Santosh S. Vempala
Computation with Sequences in the Brain. CoRR (2023)
Mirabel E. Reid, Santosh S. Vempala
The k-Cap Process on Geometric Random Graphs. COLT (2023)
Nikhil Bansal, Aditi Laddha, Santosh S. Vempala
A Unified Approach to Discrepancy Minimization. CoRR (2022)
Arun Jambulapati, Yin Tat Lee, Santosh S. Vempala
A Slightly Improved Bound for the KLS Constant. CoRR (2022)
Xinyuan Cao, Weiyang Liu, Santosh S. Vempala
Provable Lifelong Learning of Representations. AISTATS (2022)
Khashayar Gatmiry, Santosh S. Vempala
Convergence of the Riemannian Langevin Algorithm. CoRR (2022)
Ainesh Bakshi, Ilias Diakonikolas, He Jia, Daniel M. Kane, Pravesh K. Kothari, Santosh S. Vempala
arbitrary Gaussians. STOC (2022)
Yin Tat Lee, Santosh S. Vempala
The Manifold Joys of Sampling (Invited Talk). ICALP (2022)
Max Dabagia, Santosh S. Vempala, Christos H. Papadimitriou
Assemblies of neurons learn to classify well-separated distributions. COLT (2022)
Yunbum Kook, Yin Tat Lee, Ruoqi Shen, Santosh S. Vempala
Sampling with Riemannian Hamiltonian Monte Carlo in a Constrained Space. CoRR (2022)
Yunbum Kook, Yin Tat Lee, Ruoqi Shen, Santosh S. Vempala
Sampling with Riemannian Hamiltonian Monte Carlo in a Constrained Space. NeurIPS (2022)
Zongchen Chen, Santosh S. Vempala
Optimal Convergence Rate of Hamiltonian Monte Carlo for Strongly Logconcave Distributions. Theory Comput. 18 (2022)
Nikhil Bansal, Aditi Laddha, Santosh S. Vempala
A Unified Approach to Discrepancy Minimization. APPROX/RANDOM (2022)
Aditi Laddha, Mohit Singh, Santosh S. Vempala
Socially fair network design via iterative rounding. Oper. Res. Lett. 50 (5) (2022)
Samantha Petti, Santosh S. Vempala
Approximating sparse graphs: The random overlapping communities model. Random Struct. Algorithms 61 (4) (2022)
Yunbum Kook, Yin Tat Lee, Ruoqi Shen, Santosh S. Vempala
Condition-number-independent Convergence Rate of Riemannian Hamiltonian Monte Carlo with Numerical Integrators. CoRR (2022)
Ruilin Li, Molei Tao, Santosh S. Vempala, Andre Wibisono
The Mirror Langevin Algorithm Converges with Vanishing Bias. ALT (2022)
Yin Tat Lee, Santosh S. Vempala
Geodesic Walks in Polytopes. SIAM J. Comput. 51 (2) (2022)
Mirabel Reid, Santosh S. Vempala
The k-Cap Process on Geometric Random Graphs. CoRR (2022)
Shivam Garg, Santosh S. Vempala
How and When Random Feedback Works: A Case Study of Low-Rank Matrix Factorization. AISTATS (2022)
Mehrdad Ghadiri, Mohit Singh, Santosh S. Vempala
Constant-Factor Approximation Algorithms for Socially Fair k-Clustering. CoRR (2022)
Greg Bodwin, Santosh S. Vempala
A unified view of graph regularity via matrix decompositions. Random Struct. Algorithms 61 (1) (2022)
He Jia, Aditi Laddha, Yin Tat Lee, Santosh S. Vempala
) volume algorithm. STOC (2021)
Ruilin Li, Molei Tao, Santosh S. Vempala, Andre Wibisono
The Mirror Langevin Algorithm Converges with Vanishing Bias. CoRR (2021)
Shivam Garg, Santosh S. Vempala
How and When Random Feedback Works: A Case Study of Low-Rank Matrix Factorization. CoRR (2021)
Richard Peng, Santosh S. Vempala
Solving Sparse Linear Systems Faster than Matrix Multiplication. SODA (2021)
Xinyuan Cao, Weiyang Liu, Santosh S. Vempala
Provable Lifelong Learning of Representations. CoRR (2021)
Max Dabagia, Christos H. Papadimitriou, Santosh S. Vempala
Assemblies of neurons can learn to classify well-separated distributions. CoRR (2021)
Yin Tat Lee, Santosh S. Vempala
Tutorial on the Robust Interior Point Method. CoRR (2021)
Mehrdad Ghadiri, Richard Peng, Santosh S. Vempala
. CoRR (2021)
Aditi Laddha, Santosh S. Vempala
Convergence of Gibbs Sampling: Coordinate Hit-And-Run Mixes Fast. SoCG (2021)
Mehrdad Ghadiri, Samira Samadi, Santosh S. Vempala
Socially Fair k-Means Clustering. FAccT (2021)
He Jia, Aditi Laddha, Yin Tat Lee, Santosh S. Vempala
) Volume Algorithm. CoRR (2020)
Santosh S. Vempala, Ruosong Wang, David P. Woodruff
The Communication Complexity of Optimization. SODA (2020)
Richard Peng, Santosh S. Vempala
Solving Sparse Linear Systems Faster than Matrix Multiplication. CoRR (2020)
Manuel Blum, Santosh S. Vempala
The complexity of human computation via a concrete model with an application to passwords. Proc. Natl. Acad. Sci. USA 117 (17) (2020)
Aditi Laddha, Yin Tat Lee, Santosh S. Vempala
Strong self-concordance and sampling. STOC (2020)
Mehrdad Ghadiri, Samira Samadi, Santosh S. Vempala
Fair k-Means Clustering. CoRR (2020)
Ainesh Bakshi, Ilias Diakonikolas, He Jia, Daniel M. Kane, Pravesh K. Kothari, Santosh S. Vempala
Robustly Learning Mixtures of k Arbitrary Gaussians. CoRR (2020)
Aditi Laddha, Santosh S. Vempala
Convergence of Gibbs Sampling: Coordinate Hit-and-Run Mixes Fast. CoRR (2020)
Santosh S. Vempala, Andre Wibisono
Rapid Convergence of the Unadjusted Langevin Algorithm: Isoperimetry Suffices. NeurIPS (2019)
Uthaipon Tantipongpipat, Samira Samadi, Mohit Singh, Jamie Morgenstern, Santosh S. Vempala
Multi-Criteria Dimensionality Reduction with Applications to Fairness. NeurIPS (2019)
Jung Wook Park, Aditi Shah, Rosa I. Arriaga, Santosh S. Vempala
Redesigning a Basic Laboratory Information System for the Global South. ITU Kaleidoscope (2019)
Christos H. Papadimitriou, Santosh S. Vempala
Random Projection in the Brain and Computation with Assemblies of Neurons. ITCS (2019)
Santosh S. Vempala, Ruosong Wang, David P. Woodruff
The Communication Complexity of Optimization. CoRR (2019)
Greg Bodwin, Santosh S. Vempala
Matrix Decompositions and Sparse Graph Regularity. CoRR (2019)
Elan Rosenfeld, Santosh S. Vempala, Manuel Blum
Human-Usable Password Schemas: Beyond Information-Theoretic Security. CoRR (2019)
Jamie Morgenstern, Samira Samadi, Mohit Singh, Uthaipon Tao Tantipongpipat, Santosh S. Vempala
Fair Dimensionality Reduction and Iterative Rounding for SDPs. CoRR (2019)
Santosh S. Vempala, Andre Wibisono
Rapid Convergence of the Unadjusted Langevin Algorithm: Log-Sobolev Suffices. CoRR (2019)
Aditi Laddha, Yin Tat Lee, Santosh S. Vempala
Strong Self-Concordance and Sampling. CoRR (2019)
Santosh S. Vempala, John Wilmes
Gradient Descent for One-Hidden-Layer Neural Networks: Polynomial Convergence and SQ Lower Bounds. COLT (2019)
Christoph Hunkenschröder, Santosh S. Vempala, Adrian Vetta
A 4/3-Approximation Algorithm for the Minimum 2-Edge Connected Subgraph Problem. ACM Trans. Algorithms 15 (4) (2019)
Zongchen Chen, Santosh S. Vempala
Optimal Convergence Rate of Hamiltonian Monte Carlo for Strongly Logconcave Distributions. CoRR (2019)
Zongchen Chen, Santosh S. Vempala
Optimal Convergence Rate of Hamiltonian Monte Carlo for Strongly Logconcave Distributions. APPROX-RANDOM (2019)
Samantha Petti, Santosh S. Vempala
Approximating Sparse Graphs: The Random Overlapping Communities Model. CoRR (2018)
Yin Tat Lee, Zhao Song, Santosh S. Vempala
Algorithmic Theory of ODEs and Sampling from Well-conditioned Logconcave Densities. CoRR (2018)
Nima Anari, Constantinos Daskalakis, Wolfgang Maass, Christos H. Papadimitriou, Amin Saberi, Santosh S. Vempala
Smoothed Analysis of Discrete Tensor Decomposition and Assemblies of Neurons. NeurIPS (2018)
Vitaly Feldman, Will Perkins, Santosh S. Vempala
On the Complexity of Random Satisfiability Problems with Planted Solutions. SIAM J. Comput. 47 (4) (2018)
Samira Samadi, Uthaipon Tao Tantipongpipat, Jamie Morgenstern, Mohit Singh, Santosh S. Vempala
The Price of Fair PCA: One Extra dimension. NeurIPS (2018)
Samira Samadi, Santosh S. Vempala, Adam Tauman Kalai
Usability of Humanly Computable Passwords. HCOMP (2018)
Yin Tat Lee, Santosh S. Vempala
The Kannan-Lovász-Simonovits Conjecture. CoRR (2018)
Nima Anari, Constantinos Daskalakis, Wolfgang Maass, Christos H. Papadimitriou, Amin Saberi, Santosh S. Vempala
Smoothed Analysis of Discrete Tensor Decomposition and Assemblies of Neurons. CoRR (2018)
Yin Tat Lee, Aaron Sidford, Santosh S. Vempala
Efficient Convex Optimization with Membership Oracles. COLT (2018)
Yin Tat Lee, Santosh S. Vempala
Stochastic localization + Stieltjes barrier = tight bound for log-Sobolev. STOC (2018)
Santosh S. Vempala, John Wilmes
Polynomial Convergence of Gradient Descent for Training One-Hidden-Layer Neural Networks. CoRR (2018)
Santosh S. Vempala
Continuous Algorithms (Invited Paper). FSTTCS (2018)
Samira Samadi, Uthaipon Tao Tantipongpipat, Jamie Morgenstern, Mohit Singh, Santosh S. Vempala
The Price of Fair PCA: One Extra Dimension. CoRR (2018)
Cristopher Moore, Santosh S. Vempala
Special Section on the Fifty-Sixth Annual IEEE Symposium on Foundations of Computer Science (FOCS 2015). SIAM J. Comput. 47 (6) (2018)
Yin Tat Lee, Santosh S. Vempala
Convergence rate of riemannian Hamiltonian Monte Carlo and faster polytope volume computation. STOC (2018)
Robert Legenstein, Wolfgang Maass, Christos H. Papadimitriou, Santosh S. Vempala
Long Term Memory and the Densest K-Subgraph Problem. ITCS (2018)
Ben Cousins, Santosh S. Vempala
Algorithms for Volume and Gaussian Volume. SIAM J. Comput. 47 (3) (2018)
Jeremiah Blocki, Manuel Blum, Anupam Datta, Santosh S. Vempala
Towards Human Computable Passwords. ITCS (2017)
Hulda S. Haraldsdóttir, Ben Cousins, Ines Thiele, Ronan M. T. Fleming, Santosh S. Vempala
CHRR: coordinate hit-and-run with rounding for uniform sampling of constraint-based models. Bioinform. 33 (11) (2017)
Vitaly Feldman, Cristobal Guzman, Santosh S. Vempala
Statistical Query Algorithms for Mean Vector Estimation and Stochastic Convex Optimization. SODA (2017)
Vitaly Feldman, Elena Grigorescu, Lev Reyzin, Santosh S. Vempala, Ying Xiao
Statistical Algorithms and a Lower Bound for Detecting Planted Cliques. J. ACM 64 (2) (2017)
Manuel Blum, Santosh S. Vempala
The Complexity of Human Computation: A Concrete Model with an Application to Passwords. CoRR (2017)
Ravindran Kannan, Santosh S. Vempala
Randomized algorithms in numerical linear algebra. Acta Numer. 26 (2017)
Samira Samadi, Santosh S. Vempala, Adam Tauman Kalai
Usability of Humanly Computable Passwords. CoRR (2017)
Friedrich Eisenbrand, Santosh S. Vempala
Geometric random edge. Math. Program. 164 (1-2) (2017)

Santosh S. Vempala.css-eqlu8i{font-size:small;padding-left:4px;}

Publication Activity (10 Years)

Top Topics

Top Venues

Santosh S. Vempala