# Santosh Vempala

#18,896

Most Influential Person Now

Computer scientist

## Santosh Vempala's AcademicInfluence.com Rankings

Santosh Vempalacomputer-science Degrees

Computer Science

#1122

World Rank

#1162

Historical Rank

Database

#2759

World Rank

#2883

Historical Rank

## Download Badge

Computer Science

## Why Is Santosh Vempala Influential?

(Suggest an Edit or Addition)According to Wikipedia, Santosh Vempala is a prominent computer scientist. He is a Distinguished Professor of Computer Science at the Georgia Institute of Technology. His main work has been in the area of Theoretical Computer Science.

## Santosh Vempala's Published Works

### Published Works

- On clusterings-good, bad and spectral (2000) (1221)
- Latent semantic indexing: a probabilistic analysis (1998) (1102)
- Fast Monte-Carlo algorithms for finding low-rank approximations (1998) (759)
- Efficient algorithms for online decision problems (2005) (705)
- Creation and analysis of biochemical constraint-based models using the COBRA Toolbox v.3.0 (2019) (596)
- The Random Projection Method (2005) (542)
- Clustering Large Graphs via the Singular Value Decomposition (2004) (515)
- An algorithmic theory of learning: Robust concepts and random projection (1999) (394)
- The geometry of logconcave functions and sampling algorithms (2007) (372)
- Latent Semantic Indexing (2000) (345)
- Matrix approximation and projective clustering via volume sampling (2006) (335)
- Agnostic Estimation of Mean and Covariance (2016) (299)
- Filtering spam with behavioral blacklisting (2007) (291)
- Simulated annealing in convex bodies and an O*(n4) volume algorithm (2006) (283)
- Hit-and-run from a corner (2004) (263)
- Solving convex programs by random walks (2004) (240)
- A spectral algorithm for learning mixture models (2004) (232)
- Clustering in large graphs and matrices (1999) (223)
- Adaptive Sampling and Fast Low-Rank Matrix Approximation (2006) (217)
- Path splicing (2008) (213)
- A Polynomial-Time Algorithm for Learning Noisy Linear Threshold Functions (1996) (213)
- Geometric Random Walks: a Survey (2007) (200)
- Algorithmic Prediction of Health-Care Costs (2008) (187)
- On The Approximability Of The Traveling Salesman Problem (2006) (182)
- A discriminative framework for clustering via similarity functions (2008) (176)
- Efficient algorithms for universal portfolios (2000) (174)
- Fast Algorithms for Logconcave Functions: Sampling, Rounding, Integration and Optimization (2006) (173)
- Locality-preserving hashing in multidimensional spaces (1997) (173)
- The Spectral Method for General Mixture Models (2008) (167)
- Statistical Algorithms and a Lower Bound for Detecting Planted Cliques (2012) (162)
- Simple Markov-chain algorithms for generating bipartite graphs and tournaments (1997) (162)
- A spectral algorithm for learning mixtures of distributions (2002) (159)
- A divide-and-merge methodology for clustering (2005) (156)
- Kernels as features: On kernels, margins, and low-dimensional mappings (2006) (145)
- New Approximation Guarantees for Minimum-Weight k-Trees and Prize-Collecting Salesmen (1999) (144)
- Simulated Annealing for Convex Optimization (2006) (144)
- Isotropic PCA and Affine-Invariant Clustering (2008) (139)
- Spectral Algorithms (2009) (136)
- Randomized metarounding (2002) (133)
- Rapid Convergence of the Unadjusted Langevin Algorithm: Isoperimetry Suffices (2019) (128)
- Creation and analysis of biochemical constraint-based models: the COBRA Toolbox v3.0. (2017) (126)
- Chipping Away at Censorship Firewalls with User-Generated Content (2010) (125)
- A simple polynomial-time rescaling algorithm for solving linear programs (2004) (123)
- On the Complexity of Random Satisfiability Problems with Planted Solutions (2013) (117)
- Adaptive Simulated Annealing: A Near-optimal Connection between Sampling and Counting (2006) (116)
- Enumerative Lattice Algorithms in any Norm Via M-ellipsoid Coverings (2010) (105)
- The Price of Fair PCA: One Extra Dimension (2018) (102)
- Eldan's Stochastic Localization and the KLS Hyperplane Conjecture: An Improved Lower Bound for Expansion (2016) (88)
- Improved approximation guarantees for minimum-weight k-trees and prize-collecting salesmen (1995) (87)
- Convergence rate of Riemannian Hamiltonian Monte Carlo and faster polytope volume computation (2017) (86)
- Fourier PCA and robust tensor decomposition (2013) (84)
- Many sparse cuts via higher eigenvalues (2011) (84)
- A Constant-Factor Approximation Algorithm for the k-MST Problem (1999) (83)
- Principal Component Analysis and Higher Correlations for Distributed Data (2013) (79)
- Nash equilibria in random games (2005) (75)
- Simulated annealing in convex bodies and an O*(n/sup 4/) volume algorithm (2003) (75)
- An Approximation Algorithm for the Minimum-Cost k-Vertex Connected Subgraph (2003) (74)
- Simple Markov-Chain Algorithms for Generating Bipartite Graphs and Tournaments (Extended Abstract) (1999) (70)
- Semi-definite relaxations for minimum bandwidth and other vertex-ordering problems (1998) (70)
- CHRR: coordinate hit-and-run with rounding for uniform sampling of constraint-based models (2017) (70)
- Expanders via random spanning trees (2008) (68)
- Efficient Representations for Lifelong Learning and Autoencoding (2014) (67)
- A practical volume algorithm (2016) (65)
- An FPTAS for #Knapsack and Related Counting Problems (2011) (65)
- The Colin de Verdière number and sphere representations of a graph (1997) (64)
- Statistical Query Algorithms for Mean Vector Estimation and Stochastic Convex Optimization (2015) (62)
- A random sampling based algorithm for learning the intersection of half-spaces (1997) (61)
- Factor 4/3 approximations for minimum 2-connected subgraphs (2000) (60)
- Approximation algorithms for minimum-cost k-vertex connected subgraphs (2002) (60)
- The approximate rank of a matrix and its algorithmic applications: approximate rank (2013) (60)
- Hit-and-Run is Fast and Fun ∗ (2002) (59)
- On the Complexity of Learning Neural Networks (2017) (57)
- Bypassing KLS: Gaussian Cooling and an O^*(n3) Volume Algorithm (2014) (56)
- Socially Fair k-Means Clustering (2020) (56)
- A constant-factor approximation for the k-MST problem in the plane (1995) (54)
- Brain computation by assemblies of neurons (2019) (54)
- A divide-and-merge methodology for clustering (2006) (53)
- Integer programming, lattice algorithms, and deterministic volume estimation (2012) (53)
- Optimal Convergence Rate of Hamiltonian Monte Carlo for Strongly Logconcave Distributions (2019) (53)
- Tensor decomposition and approximation schemes for constraint satisfaction problems (2005) (52)
- The Spectral Method for General Mixture Models (2005) (52)
- Network Design Via Iterative Rounding Of Setpair Relaxations (2006) (51)
- Randomized algorithms in numerical linear algebra (2017) (49)
- Algorithms for implicit hitting set problems (2011) (46)
- Random projection: a new approach to VLSI layout (1998) (46)
- Efficient Convex Optimization with Membership Oracles (2017) (44)
- A random-sampling-based algorithm for learning intersections of halfspaces (2010) (43)
- Optimal outlier removal in high-dimensional spaces (2004) (42)
- On the approximability of the traveling salesman problem (extended abstract) (2000) (41)
- Hit-and-Run is Fast and Fun 1 (2003) (41)
- Improved approximation algorithms for biconnected subgraphs via better lower bounding techniques (1993) (41)
- A Deterministic Polynomial-Time Approximation Scheme for Counting Knapsack Solutions (2010) (40)
- On Euclidean Embeddings and Bandwidth Minimization (2001) (39)
- The Complexity of Approximating Vertex Expansion (2013) (39)
- Random Tensors and Planted Cliques (2009) (38)
- Path Splicing: Reliable Connectivity with Rapid Recovery (2007) (38)
- Recent Progress and Open Problems in Algorithmic Convex Geometry (2010) (38)
- On the Held-Karp relaxation for the asymmetric and symmetric traveling salesman problems (2003) (37)
- Geodesic walks in polytopes (2016) (37)
- An Efficient Re-Scaled Perceptron Algorithm for Conic Systems (2006) (37)
- A Cubic Algorithm for Computing Gaussian Volume (2013) (37)
- Solving convex programs by random walks (2002) (36)
- Local versus global properties of metric spaces (2006) (35)
- A constant-factor approximation algorithm for the k MST problem (extended abstract) (1996) (35)
- Fences Are Futile: On Relaxations for the Linear Ordering Problem (2001) (35)
- Towards a 4/3 approximation for the asymmetric traveling salesman problem (1999) (34)
- Sampling lattice points (1997) (34)
- Statistical Algorithms and a Lower Bound for Planted Clique (2012) (34)
- Algorithmic Theory of ODEs and Sampling from Well-conditioned Logconcave Densities (2018) (33)
- Gradient Descent for One-Hidden-Layer Neural Networks: Polynomial Convergence and SQ Lower Bounds (2018) (33)
- The Kannan-Lovász-Simonovits Conjecture (2018) (32)
- Structure from Local Optima: Learning Subspace Juntas via Higher Order PCA (2011) (31)
- LifeNet: a flexible ad hoc networking solution for transient environments (2011) (30)
- Creation and analysis of biochemical constraint-based models : the COBRA Toolbox v 3 . 0 26 th February 2018 (2018) (30)
- On Kernels, Margins, and Low-Dimensional Mappings (2004) (29)
- Learning Convex Concepts from Gaussian Distributions with PCA (2010) (29)
- Robustly learning mixtures of k arbitrary Gaussians (2020) (27)
- Statistical algorithms and a lower bound for detecting planted cliques (2012) (27)
- Multi-Criteria Dimensionality Reduction with Applications to Fairness (2019) (27)
- Solving Sparse Linear Systems Faster than Matrix Multiplication (2020) (27)
- A note on non-degenerate integer programs with small sub-determinants (2016) (26)
- Near-optimal deterministic algorithms for volume computation via M-ellipsoids (2012) (26)
- Geometric algorithms for online optimization (2002) (26)
- Approximating Multicast Congestion (1999) (26)
- Algorithmic Extensions of Cheeger's Inequality to Higher Eigenvalues and Partitions (2011) (26)
- The Communication Complexity of Optimization (2019) (26)
- The Geometry of Logconcave Functions and an O* (n 3 ) Sampling Algorithm (2003) (25)
- Randomized metarounding (extended abstract) (2000) (25)
- Random Projection in the Brain and Computation with Assemblies of Neurons (2019) (24)
- Stochastic localization + Stieltjes barrier = tight bound for log-Sobolev (2017) (24)
- Logconcave functions: geometry and efficient sampling algorithms (2003) (24)
- Testing Geometric Convexity (2004) (24)
- Reducing isotropy and volume to KLS: an o*(n3ψ2) volume algorithm (2020) (23)
- Gaussian Cooling and O*(n3) Algorithms for Volume and Gaussian Volume (2014) (21)
- Randomly-oriented k-d Trees Adapt to Intrinsic Dimension (2012) (21)
- Polynomial Convergence of Gradient Descent for Training One-Hidden-Layer Neural Networks (2018) (21)
- Subsampled Power Iteration: a Unified Algorithm for Block Models and Planted CSP's (2014) (20)
- Dispersion of Mass and the Complexity of Randomized Geometric Algorithms (2006) (20)
- Statistical Query Algorithms for Stochastic Convex Optimization (2015) (20)
- Eecient Algorithms for Online Decision Problems (2003) (20)
- On Noise-Tolerant Learning of Sparse Parities and Related Problems (2011) (20)
- Publishable Humanly Usable Secure Password Creation Schemas (2015) (19)
- A 4/3-Approximation Algorithm for the Minimum 2-Edge Connected Subgraph Problem (2019) (19)
- Strong self-concordance and sampling (2019) (19)
- A convex relaxation for the asymmetric TSP (1999) (18)
- Long Term Memory and the Densest K-Subgraph Problem (2018) (17)
- The Cutting Plane Method Is Polynomial for Perfect Matchings (2012) (17)
- Flow metrics (2002) (17)
- A New Approach to Strongly Polynomial Linear Programming (2010) (16)
- Cortical Learning via Prediction (2015) (16)
- The complexity of human computation via a concrete model with an application to passwords (2017) (16)
- Thin partitions: isoperimetric inequalities and a sampling algorithm for star shaped bodies (2010) (15)
- A Constant-Factor Approximation Algorithm for the Geometric k-MST Problem in the Plane (1999) (15)
- Deterministic construction of an approximate M-ellipsoid and its applications to derandomizing lattice algorithms (2011) (15)
- Smoothed Analysis of Discrete Tensor Decomposition and Assemblies of Neurons (2018) (15)
- Visual Categorization with Random Projection (2015) (14)
- Sampling with Riemannian Hamiltonian Monte Carlo in a Constrained Space (2022) (14)
- Random Sampling of Euler Tours (1997) (14)
- The Mirror Langevin Algorithm Converges with Vanishing Bias (2021) (14)
- Towards Human Computable Passwords (2014) (13)
- Assembly pointers for variable binding in networks of spiking neurons (2016) (13)
- Convergence of Gibbs Sampling: Coordinate Hit-and-Run Mixes Fast (2020) (13)
- Eldan's Stochastic Localization and the KLS Conjecture: Isoperimetry, Concentration and Mixing (2016) (13)
- Stochastic Billiards for Sampling from the Boundary of a Convex Set (2014) (12)
- On Nash-Equilibria of Approximation-Stable Games (2010) (12)
- Enumerative Algorithms for the Shortest and Closest Lattice Vector Problems in Any Norm via M-Ellipsoid Coverings (2010) (11)
- Sampling s-Concave Functions: The Limit of Convexity Based Isoperimetry (2009) (11)
- Matrix Approximation and Projective Clustering via Iterative Sampling (2005) (11)
- The Kannan-Lov\'asz-Simonovits Conjecture. (2018) (11)
- Rapid Convergence of the Unadjusted Langevin Algorithm: Log-Sobolev Suffices (2019) (11)
- The Spectral Method for Mixture Models (2004) (10)
- Optimal outlier removal in high-dimensional (2001) (10)
- Nimble Algorithms for Cloud Computing (2013) (10)
- A Slightly Improved Bound for the KLS Constant (2022) (10)
- Semantic Communication for Simple Goals Is Equivalent to On-line Learning (2011) (10)
- Edge Covers of Setpairs and the Iterative Rounding Method (2001) (10)
- Brain Computation: A Computer Science Perspective (2019) (9)
- Fair Dimensionality Reduction and Iterative Rounding for SDPs (2019) (9)
- Clustering via Similarity Functions : Theoretical Foundations and Algorithms ∗ (2008) (9)
- Max vs Min: Tensor Decomposition and ICA with nearly Linear Sample Complexity (2014) (9)
- Where to Start a Geometric Random Walk (2003) (8)
- Usability of Humanly Computable Passwords (2017) (7)
- Accelerated Newton Iteration for Roots of Black Box Polynomials (2016) (7)
- A Generalized Central Limit Conjecture for Convex Bodies (2019) (7)
- Beyond Spectral: Tight Bounds for Planted Gaussians (2016) (6)
- Convergence of the Riemannian Langevin Algorithm (2022) (6)
- Logconcave random graphs (2008) (6)
- Integer feasibility of random polytopes: random integer programs (2011) (6)
- Provable Lifelong Learning of Representations (2021) (6)
- Subsampled Power Iteration: a New Algorithm for Block Models and Planted CSP's (2014) (6)
- C4G BLIS: Health Care Delivery via Iterative Collaborative Design in Resource-constrained Settings (2016) (6)
- A Limited-Backtrack Greedy Schema for Approximation Algorithms (1994) (6)
- Robustly Clustering a Mixture of Gaussians (2019) (6)
- A Polynomial-time Rescaling Algorithm for Solving Linear Programs (2003) (6)
- Approximating sparse graphs: The random overlapping communities model (2018) (6)
- Spectral Algorithms for Learning and Clustering (2007) (6)
- Life (and routing) on the Wireless Manifold (2007) (6)
- Assemblies of neurons can learn to classify well-separated distributions (2021) (5)
- Design and deployment of a blood safety monitoring tool (2009) (5)
- A Discrepancy based Approach to Integer Programming (2011) (5)
- Max vs Min: Independent Component Analysis with nearly Linear Sample Complexity (2014) (5)
- Thin Partitions: Isoperimetric Inequalities and Sampling Algorithms for some Nonconvex Families (2009) (4)
- Integer Feasibility of Random Polytopes (2011) (4)
- A Theory of Similarity Functions for Clustering (2007) (4)
- Accelerated Newton Iteration: Roots of Black Box Polynomials and Matrix Eigenvalues (2015) (4)
- A geometric theory of outliers and perturbation (2002) (4)
- Complexity of learning subspace juntas and ICA (2013) (4)
- Constant-Factor Approximation Algorithms for Socially Fair k-Clustering (2022) (3)
- Tutorial on the Robust Interior Point Method (2021) (3)
- Cortical Computation (2015) (3)
- Condition-number-independent Convergence Rate of Riemannian Hamiltonian Monte Carlo with Numerical Integrators (2022) (3)
- Symmetric network computation (2006) (3)
- Modeling high-dimensional data (2012) (3)
- A unified view of graph regularity via matrix decompositions (2019) (3)
- Cortical Computation via Iterative Constructions (2016) (3)
- Local versus Global Properties of Metric Spaces Extended abstract (2005) (3)
- Sparse Regression Faster than dω (2021) (3)
- Chi-squared Amplification: Identifying Hidden Hubs (2016) (3)
- Better Interdomain Path Diversity with BGP Path Splicing (2007) (2)
- Mechanistic model-driven exometabolomic characterisation of human dopaminergic neuronal metabolism (2021) (2)
- The Hidden Hubs Problem (2017) (2)
- Dispersion of Mass and the Complexity of Randomized Algorithms (2006) (2)
- The Joy of PCA (2010) (2)
- Circumventing censorship with collage (2010) (2)
- Random Overlapping Communities: Approximating Motif Densities of Large Graphs (2017) (2)
- MyMANET : A Customizable Mobile Ad hoc Network (2009) (2)
- Fair k-Means Clustering (2020) (2)
- Biologically Plausible Neural Networks via Evolutionary Dynamics and Dopaminergic Plasticity (2019) (2)
- Assembly projections support the assignment of thematic roles to concepts in networks of spiking neurons (2016) (2)
- Faster $p$-Norm Regression Using Sparsity (2021) (2)
- How and When Random Feedback Works: A Case Study of Low-Rank Matrix Factorization (2021) (2)
- The Manifold Joys of Sampling (2022) (2)
- Is Planted Coloring Easier than Planted Clique? (2023) (1)
- Eldan's Stochastic Localization and the KLS Hyperplane Conjecture: An Almost Constant Lower Bound for Expansion (2016) (1)
- Reducing Isotropy and Volume to KLS: An $O(n^3\psi^2)$ Volume Algorithm (2020) (1)
- E cient Singular Value Decompositionvia Improved Document SamplingFan (1999) (1)
- Efficient Convex Optimization with Oracles (2019) (1)
- Variable Binding through Assemblies in Spiking Neural Networks (2016) (1)
- A Polynomial-time Algorithm for Learning Noisy LinearThreshold Fun tions (1996) (1)
- Combinatorial Optimization Approximation Algorithms (1)
- Finding Sparse Cuts via Cheeger Inequalities for Higher Eigenvalues (2012) (1)
- Unsupervised Learning through Prediction in a Model of Cortex (2014) (1)
- A Unified Approach to Discrepancy Minimization (2022) (1)
- The Manifold Joys of Sampling (Invited Talk) (2022) (1)
- A Learning Theoretic Framework for Clustering with Similarity Functions (2007) (1)
- The Complexity of Statistical Algorithms (2012) (1)
- Isotropic PCA and Affine-Invariant Clustering (Extended Abstract) (2008) (1)
- Building Consensus with Balanced Splits ⋆ (2014) (0)
- Frontmatter, Table of Contents, Preface, Organization, External Reviewers, List of Authors (2017) (0)
- Random Sampling of Euler Tours 1 (0)
- Sampling Harmonic Concave Functions: The Limit of Convexity Based Isoperimetry (2009) (0)
- Approximation Algorithms 1.1 Minimum Vertex Cover (2004) (0)
- Algorithmic Theories of (1999) (0)
- Session details: Session 10A (2007) (0)
- Phase Transition in Random Integer Programs (2012) (0)
- Spectral Algorithms (draft) (2010) (0)
- Proceeding of the Annual ACM-SIAM Symposium on Discrete Algorithms: Preface (2005) (0)
- Combinatorial Optimization The Primal-dual Algorithm November 2 Lecturer : (2004) (0)
- Creation and analysis of biochemical constraint-based models using the COBRA Toolbox v.3.0 (2019) (0)
- The Limit of Convexity Based Isoperimetry: Sampling Harmonic-Concave Functions (2009) (0)
- Adaptive Matrix Vector Product (2017) (0)
- Geometric Tools for Algorithms. (1997) (0)
- A Calculus for Brain Computation (2019) (0)
- Design of a blood flow system (2009) (0)
- Sampling with Barriers: Faster Mixing via Lewis Weights (2023) (0)
- Arid Prize-collecting S-aksmen (0)
- A practical volume algorithm (2015) (0)
- The Complexity of the Cutting Plane Method (2011) (0)
- Query Complexity of Sampling and Small Geometric Partitions (2014) (0)
- Session details: Session 8B (2003) (0)
- A Dynamic Reputation Service for Spotting Spammers (2008) (0)
- A Computer Science View of the Brain (2017) (0)
- Rounding via random projection (2005) (0)
- Continuous Algorithms (Invited Paper) (2018) (0)
- Structure from Local Optima: Factoring Distributions and Learning Subspace Juntas (Extended version) (2022) (0)
- Redesigning a Basic Laboratory Information System for the Global South (2019) (0)
- Session details: Session 6A (2003) (0)
- Intersections of half-spaces (2005) (0)
- Indexing and clustering (2005) (0)
- Fen es Are Futile : On Relaxations for the LinearOrdering (2007) (0)
- Effective Principal Component Analysis (2012) (0)
- Special Section on the Fifty-Sixth Annual IEEE Symposium on Foundations of Computer Science (FOCS 2015) (2018) (0)
- Embedding metrics in Euclidean space (2005) (0)
- Spectral Algorithms and Representations Lecture 4: Constant Time Svd Approximation (0)
- Clustering via Matrix Exponentiation (0)
- A probabilistic analysis for the Feedback Vertex Set problem (2009) (0)
- The k-Cap Process on Geometric Random Graphs (2022) (0)
- Beyond Moments: Robustly Learning Affine Transformations with Asymptotically Optimal Error (2023) (0)
- N C ] 1 1 N ov 2 01 6 Assembly pointers for variable binding in networks of spiking neurons (2016) (0)
- Combinatorial Optimization The Primal-dual Algorithm (2004) (0)
- Deterministic 2^{O(n)} Algorithms for M-Ellipsoids, Lattice Problems and Volume Estimation (2012) (0)
- Matrix Decompositions and Sparse Graph Regularity (2019) (0)
- Socially fair network design via iterative rounding (2022) (0)
- N ov 2 01 9 Matrix Decompositions and Sparse Graph Regularity ∗ (2019) (0)
- Workload Generation and Instrumentation for Reproducible Networking Experiments (2009) (0)
- Spectral Algorithms and Representations April 2005 The Colin de Verdière Number and Nullspace Embeddings (2005) (0)
- The Bit Complexity of Efficient Continuous Optimization (2023) (0)
- Subsampled Power Iteration: a Unified Algorithm for Block Models and Planted CSP\textquotesingle s (2015) (0)
- Corrigendum: A Random Sampling Algorithm for Learning an Intersection of Halfspaces (2010) (0)
- Human-Usable Password Schemas: Beyond Information-Theoretic Security (2019) (0)
- Euclidean embeddings: Beyond distance preservation (2005) (0)

This paper list is powered by the following services:

## Other Resources About Santosh Vempala

## What Schools Are Affiliated With Santosh Vempala?

Santosh Vempala is affiliated with the following schools: