| 2026 | COLT | The Geometry of Efficient Nonconvex Sampling. | Santosh S. Vempala, Andre Wibisono |
| 2026 | STOC | Provable Long-Range Benefits of Next-Token Prediction. | Xinyuan Cao, Santosh S. Vempala |
| 2025 | AAAI | Does GPT Really Get It? A Hierarchical Scale to Quantify Human and AI's Understanding of Algorithms. | Mirabel Reid, Santosh S. Vempala |
| 2025 | FOCS | Faster Logconcave Sampling from a Cold Start in High Dimension. | Yunbum Kook, Santosh S. Vempala |
| 2025 | STOC | Sampling and Integration of Logconcave Functions by Algorithmic Diffusion. | Yunbum Kook, Santosh S. Vempala |
| 2024 | ALT | Computation with Sequences of Assemblies in a Model of the Brain. | Max Dabagia, Christos H. Papadimitriou, Santosh S. Vempala |
| 2024 | COLT | Sampling Polytopes with Riemannian HMC: Faster Mixing via the Lewis Weights Barrier. | Khashayar Gatmiry, Jonathan A. Kelner, Santosh S. Vempala |
| 2024 | COLT | Gaussian Cooling and Dikin Walks: The Interior-Point Method for Logconcave Sampling. | Yunbum Kook, Santosh S. Vempala |
| 2024 | STOC | Calibrated Language Models Must Hallucinate. | Adam Tauman Kalai, Santosh S. Vempala |
| 2023 | COLT | Condition-number-independent Convergence Rate of Riemannian Hamiltonian Monte Carlo with Numerical Integrators. | Yunbum Kook, Yin Tat Lee, Ruoqi Shen, Santosh S. Vempala |
| 2023 | COLT | Is Planted Coloring Easier than Planted Clique? | Pravesh Kothari, Santosh S. Vempala, Alexander S. Wein, Jeff Xu |
| 2023 | COLT | The k-Cap Process on Geometric Random Graphs. | Mirabel E. Reid, Santosh S. Vempala |
| 2023 | FOCS | The Bit Complexity of Efficient Continuous Optimization. | Mehrdad Ghadiri, Richard Peng, Santosh S. Vempala |
| 2023 | FOCS | Beyond Moments: Robustly Learning Affine Transformations with Asymptotically Optimal Error. | He Jia, Pravesh K. Kothari, Santosh S. Vempala |
| 2022 | AISTATS | Provable Lifelong Learning of Representations. | Xinyuan Cao, Weiyang Liu, Santosh S. Vempala |
| 2022 | AISTATS | How and When Random Feedback Works: A Case Study of Low-Rank Matrix Factorization. | Shivam Garg, Santosh S. Vempala |
| 2022 | ALT | The Mirror Langevin Algorithm Converges with Vanishing Bias. | Ruilin Li, Molei Tao, Santosh S. Vempala, Andre Wibisono |
| 2022 | COLT | Assemblies of neurons learn to classify well-separated distributions. | Max Dabagia, Santosh S. Vempala, Christos H. Papadimitriou |
| 2022 | ICALP | The Manifold Joys of Sampling (Invited Talk). | Yin Tat Lee, Santosh S. Vempala |
| 2022 | STOC | Robustly learning mixtures of | Ainesh Bakshi, Ilias Diakonikolas, He Jia, Daniel M. Kane, Pravesh K. Kothari, Santosh S. Vempala |
| 2021 | SODA | Solving Sparse Linear Systems Faster than Matrix Multiplication. | Richard Peng, Santosh S. Vempala |
| 2021 | STOC | Reducing isotropy and volume to KLS: an | He Jia, Aditi Laddha, Yin Tat Lee, Santosh S. Vempala |
| 2020 | SODA | The Communication Complexity of Optimization. | Santosh S. Vempala, Ruosong Wang, David P. Woodruff |
| 2020 | STOC | Strong self-concordance and sampling. | Aditi Laddha, Yin Tat Lee, Santosh S. Vempala |
| 2019 | COLT | Gradient Descent for One-Hidden-Layer Neural Networks: Polynomial Convergence and SQ Lower Bounds. | Santosh S. Vempala, John Wilmes |
| 2018 | COLT | Efficient Convex Optimization with Membership Oracles. | Yin Tat Lee, Aaron Sidford, Santosh S. Vempala |
| 2018 | HCOMP | Usability of Humanly Computable Passwords. | Samira Samadi, Santosh S. Vempala, Adam Tauman Kalai |
| 2018 | STOC | Convergence rate of riemannian Hamiltonian Monte Carlo and faster polytope volume computation. | Yin Tat Lee, Santosh S. Vempala |
| 2018 | STOC | Stochastic localization + Stieltjes barrier = tight bound for log-Sobolev. | Yin Tat Lee, Santosh S. Vempala |
| 2017 | COLT | The Hidden Hubs Problem. | Ravindran Kannan, Santosh S. Vempala |
| 2017 | SODA | Statistical Query Algorithms for Mean Vector Estimation and Stochastic Convex Optimization. | Vitaly Feldman, Cristbal Guzmn, Santosh S. Vempala |
| 2017 | SODA | Adaptive Matrix Vector Product. | Santosh S. Vempala, David P. Woodruff |
| 2017 | STOC | Geodesic walks in polytopes. | Yin Tat Lee, Santosh S. Vempala |
| 2016 | COLT | Cortical Computation via Iterative Constructions. | Christos H. Papadimitriou, Samantha Petti, Santosh S. Vempala |
| 2016 | FOCS | Agnostic Estimation of Mean and Covariance. | Kevin A. Lai, Anup B. Rao, Santosh S. Vempala |
| 2016 | FOCS | Accelerated Newton Iteration for Roots of Black Box Polynomials. | Anand Louis, Santosh S. Vempala |
| 2016 | ICTD | C4G BLIS: Health Care Delivery via Iterative Collaborative Design in Resource-constrained Settings. | Santosh S. Vempala, Naomi Chopra, Aishwarya Rajagopal, John Nkengasong, Sidney Akuro |
| 2015 | COLT | Efficient Representations for Lifelong Learning and Autoencoding. | Maria-Florina Balcan, Avrim Blum, Santosh S. Vempala |
| 2015 | COLT | Cortical Learning via Prediction. | Christos H. Papadimitriou, Santosh S. Vempala |
| 2015 | COLT | Max vs Min: Tensor Decomposition and ICA with nearly Linear Sample Complexity. | Santosh S. Vempala, Ying Xiao |
| 2015 | PODC | Cortical Computation. | Christos H. Papadimitriou, Santosh S. Vempala |
| 2015 | STOC | Bypassing KLS: Gaussian Cooling and an O^*(n3) Volume Algorithm. | Benjamin Cousins, Santosh S. Vempala |
| 2015 | STOC | On the Complexity of Random Satisfiability Problems with Planted Solutions. | Vitaly Feldman, Will Perkins, Santosh S. Vempala |
| 2014 | COLT | Principal Component Analysis and Higher Correlations for Distributed Data. | Ravi Kannan, Santosh S. Vempala, David P. Woodruff |
| 2014 | SODA | A Cubic Algorithm for Computing Gaussian Volume. | Ben Cousins, Santosh S. Vempala |
| 2014 | STOC | Fourier PCA and robust tensor decomposition. | Navin Goyal, Santosh S. Vempala, Ying Xiao |
| 2013 | ACSSC | Complexity of learning subspace juntas and ICA. | Santosh S. Vempala, Ying Xiao |
| 2013 | FOCS | The Complexity of Approximating Vertex Expansion. | Anand Louis, Prasad Raghavendra, Santosh S. Vempala |
| 2013 | STOC | The approximate rank of a matrix and its algorithmic applications: approximate rank. | Noga Alon, Troy Lee, Adi Shraibman, Santosh S. Vempala |
| 2013 | STOC | Statistical algorithms and a lower bound for detecting planted cliques. | Vitaly Feldman, Elena Grigorescu, Lev Reyzin, Santosh S. Vempala, Ying Xiao |
| 2012 | FOCS | The Cutting Plane Method Is Polynomial for Perfect Matchings. | Karthekeyan Chandrasekaran, Lszl A. Vgh, Santosh S. Vempala |
| 2012 | SODA | Deterministic construction of an approximate M-ellipsoid and its applications to derandomizing lattice algorithms. | Daniel Dadush, Santosh S. Vempala |
| 2012 | STOC | Many sparse cuts via higher eigenvalues. | Anand Louis, Prasad Raghavendra, Prasad Tetali, Santosh S. Vempala |
| 2012 | SISAP | Effective Principal Component Analysis. | Santosh S. Vempala |
| 2011 | ALT | On Noise-Tolerant Learning of Sparse Parities and Related Problems. | Elena Grigorescu, Lev Reyzin, Santosh S. Vempala |
| 2011 | ALT | Semantic Communication for Simple Goals Is Equivalent to On-line Learning. | Brendan Juba, Santosh S. Vempala |
| 2011 | FOCS | Enumerative Lattice Algorithms in any Norm Via M-ellipsoid Coverings. | Daniel Dadush, Chris Peikert, Santosh S. Vempala |
| 2011 | FOCS | An FPTAS for #Knapsack and Related Counting Problems. | Parikshit Gopalan, Adam R. Klivans, Raghu Meka, Daniel Stefankovic, Santosh S. Vempala, Eric Vigoda |
| 2011 | SODA | Algorithms for Implicit Hitting Set Problems. | Karthekeyan Chandrasekaran, Richard M. Karp, Erick Moreno-Centeno, Santosh S. Vempala |
| 2011 | SIGCOMM | LifeNet: a flexible ad hoc networking solution for transient environments. | Hrushikesh Mehendale, Ashwin Paranjpe, Santosh S. Vempala |
| 2010 | FOCS | Corrigendum: A Random Sampling Algorithm for Learning an Intersection of Halfspaces. | Santosh S. Vempala |
| 2010 | FOCS | Learning Convex Concepts from Gaussian Distributions with PCA. | Santosh S. Vempala |
| 2010 | SODA | Thin Partitions: Isoperimetric Inequalities and a Sampling Algorithm for Star Shaped Bodies. | Karthekeyan Chandrasekaran, Daniel Dadush, Santosh S. Vempala |
| 2010 | SIGCOMM | Circumventing censorship with collage. | Sam Burnett, Nick Feamster, Santosh S. Vempala |
| 2010 | SAGT | On Nash-Equilibria of Approximation-Stable Games. | Pranjal Awasthi, Maria-Florina Balcan, Avrim Blum, Or Sheffet, Santosh S. Vempala |
| 2009 | ICTD | Design of a blood flow system. | Adebola Osuntogun, Stephen Thomas, John Pitman, Sridhar Basavaraju, Bright Mulenga, Santosh S. Vempala |
| 2009 | ICTD | Design and deployment of a blood safety monitoring tool. | Stephen Thomas, Adebola Osuntogun, John Pitman, Bright Mulenga, Santosh S. Vempala |
| 2009 | SODA | Expanders via random spanning trees. | Navin Goyal, Luis Rademacher, Santosh S. Vempala |
| 2008 | FOCS | Isotropic PCA and Affine-Invariant Clustering. | S. Charles Brubaker, Santosh S. Vempala |
| 2008 | STOC | A discriminative framework for clustering via similarity functions. | Maria-Florina Balcan, Avrim Blum, Santosh S. Vempala |
| 2008 | STOC | Logconcave random graphs. | Alan M. Frieze, Santosh S. Vempala, Juan Vera |
| 2008 | SIGCOMM | Path splicing. | Murtaza Motiwala, Megan Elmore, Nick Feamster, Santosh S. Vempala |
| 2007 | CCS | Filtering spam with behavioral blacklisting. | Anirudh Ramachandran, Nick Feamster, Santosh S. Vempala |
| 2007 | COLT | An Efficient Re-scaled Perceptron Algorithm for Conic Systems. | Alexandre Belloni, Robert M. Freund, Santosh S. Vempala |
| 2007 | COLT | Spectral Algorithms for Learning and Clustering. | Santosh S. Vempala |
| 2007 | FOCS | Adaptive Simulated Annealing: A Near-optimal Connection between Sampling and Counting. | Daniel Stefankovic, Santosh S. Vempala, Eric Vigoda |
| 2007 | HOTNETS | Life (and routing) on the Wireless Manifold. | Varun Kanade, Santosh S. Vempala |
| 2007 | HOTNETS | Path Splicing: Reliable Connectivity with Rapid Recovery. | Murtaza Motiwala, Nick Feamster, Santosh S. Vempala |
| 2006 | FOCS | Fast Algorithms for Logconcave Functions: Sampling, Rounding, Integration and Optimization. | Lszl Lovsz, Santosh S. Vempala |
| 2006 | FOCS | Dispersion of Mass and the Complexity of Randomized Geometric Algorithms. | Luis Rademacher, Santosh S. Vempala |
| 2006 | SODA | Local versus global properties of metric spaces. | Sanjeev Arora, Lszl Lovsz, Ilan Newman, Yuval Rabani, Yuri Rabinovich, Santosh S. Vempala |
| 2006 | SODA | Matrix approximation and projective clustering via volume sampling. | Amit Deshpande, Luis Rademacher, Santosh S. Vempala, Grant Wang |
| 2006 | SPAA | Symmetric network computation. | David Pritchard, Santosh S. Vempala |
| 2005 | COLT | The Spectral Method for General Mixture Models. | Ravindran Kannan, Hadi Salmasian, Santosh S. Vempala |
| 2005 | FOCS | Nash Equilibria in Random Games. | Imre Brny, Santosh S. Vempala, Adrian Vetta |
| 2005 | PODS | A divide-and-merge methodology for clustering. | David Cheng, Santosh S. Vempala, Ravi Kannan, Grant Wang |
| 2005 | STOC | Tensor decomposition and approximation schemes for constraint satisfaction problems. | Wenceslas Fernandez de la Vega, Marek Karpinski, Ravi Kannan, Santosh S. Vempala |
| 2004 | ALT | On Kernels, Margins, and Low-Dimensional Mappings. | Maria-Florina Balcan, Avrim Blum, Santosh S. Vempala |
| 2004 | STOC | A simple polynomial-time rescaling algorithm for solving linear programs. | John Dunagan, Santosh S. Vempala |
| 2004 | STOC | Hit-and-run from a corner. | Lszl Lovsz, Santosh S. Vempala |
| 2003 | COLT | Efficient Algorithms for Online Decision Problems. | Adam Kalai, Santosh S. Vempala |
| 2003 | FOCS | Simulated Annealing in Convex Bodies and an 0*(n4) Volume Algorithm. | Lszl Lovsz, Santosh S. Vempala |
| 2003 | FOCS | Logconcave Functions: Geometry and Efficient Sampling Algorithms | Lszl Lovsz, Santosh S. Vempala |
| 2002 | FOCS | A Spectral Algorithm for Learning Mixtures of Distributions. | Santosh S. Vempala, Grant Wang |
| 2002 | LATIN | Flow Metrics. | Claudson F. Bornstein, Santosh S. Vempala |
| 2002 | STOC | Solving convex programs by random walks. | Dimitris Bertsimas, Santosh S. Vempala |
| 2002 | STOC | Approximation algorithms for minimum-cost k-vertex connected subgraphs. | Joseph Cheriyan, Santosh S. Vempala, Adrian Vetta |
| 2001 | IPCO | Edge Covers of Setpairs and the Iterative Rounding Method. | Joseph Cheriyan, Santosh S. Vempala |
| 2001 | IPCO | Fences Are Futile: On Relaxations for the Linear Ordering Problem. | Alantha Newman, Santosh S. Vempala |
| 2001 | STOC | Optimal outlier removal in high-dimensional. | John Dunagan, Santosh S. Vempala |
| 2000 | FOCS | Efficient Algorithms for Universal Portfolios. | Adam Kalai, Santosh S. Vempala |
| 2000 | FOCS | On Clusterings - Good, Bad and Spectral. | Ravi Kannan, Santosh S. Vempala, Adrian Vetta |
| 2000 | SODA | Towards a 4/3 approximation for the asymmetric traveling salesman problem. | Robert D. Carr, Santosh S. Vempala, Jacques Mandler |
| 2000 | STOC | Randomized metarounding (extended abstract). | Robert D. Carr, Santosh S. Vempala |
| 2000 | STOC | On the approximability of the traveling salesman problem (extended abstract). | Christos H. Papadimitriou, Santosh S. Vempala |
| 1999 | FOCS | An Algorithmic Theory of Learning: Robust Concepts and Random Projection. | Rosa I. Arriaga, Santosh S. Vempala |
| 1999 | ISAAC | Approximating Multicast Congestion. | Santosh S. Vempala, Berthold Vcking |
| 1999 | SODA | Clustering in Large Graphs and Matrices. | Petros Drineas, Alan M. Frieze, Ravi Kannan, Santosh S. Vempala, V. Vinay |
| 1999 | SODA | A Convex Relaxation for the Asymmetric TSP. | Santosh S. Vempala, Mihalis Yannakakis |
| 1998 | FOCS | Fast Monte-Carlo Algorithms for Finding Low-Rank Approximations. | Alan M. Frieze, Ravi Kannan, Santosh S. Vempala |
| 1998 | FOCS | Random Projection: A New Approach to VLSI Layout. | Santosh S. Vempala |
| 1998 | PODS | Latent Semantic Indexing: A Probabilistic Analysis. | Christos H. Papadimitriou, Prabhakar Raghavan, Hisao Tamaki, Santosh S. Vempala |
| 1998 | STOC | Semi-Definite Relaxations for Minimum Bandwidth and other Vertex-Ordering Problems. | Avrim Blum, Goran Konjevod, R. Ravi, Santosh S. Vempala |
| 1997 | FOCS | A Random Sampling Based Algorithm for Learning the Intersection of Half-spaces. | Santosh S. Vempala |
| 1997 | SODA | Simple Markov-Chain Algorithms for Generating Bipartite Graphs and Tournaments (Extended Abstract). | Ravi Kannan, Prasad Tetali, Santosh S. Vempala |
| 1997 | STOC | Locality-Preserving Hashing in Multidimensional Spaces. | Piotr Indyk, Rajeev Motwani, Prabhakar Raghavan, Santosh S. Vempala |
| 1997 | STOC | Sampling Lattice Points. | Ravi Kannan, Santosh S. Vempala |
| 1996 | FOCS | A Polynomial-Time Algorithm for Learning Noisy Linear Threshold Functions. | Avrim Blum, Alan M. Frieze, Ravi Kannan, Santosh S. Vempala |
| 1996 | STOC | A Constant-factor Approximation Algorithm for the | Avrim Blum, R. Ravi, Santosh S. Vempala |
| 1995 | STOC | Improved approximation guarantees for minimum-weight | Baruch Awerbuch, Yossi Azar, Avrim Blum, Santosh S. Vempala |
| 1995 | STOC | A constant-factor approximation for the | Avrim Blum, Prasad Chalasani, Santosh S. Vempala |
| 1993 | SODA | Improved Approximation Algorithms for Biconnected Subgraphs via Better Lower Bounding Techniques. | Naveen Garg, Santosh S. Vempala, Aman Singla |