Santosh Vempala

Q: What Schools Are Affiliated With Santosh Vempala

Santosh Vempala is affiliated with the following schools: Massachusetts Institute of Technology, Carnegie Mellon University, Georgia Tech

Santosh Vempala's AcademicInfluence.com Rankings

Santosh Vempala

Computer Science

#1122

World Rank

#1162

Historical Rank

Database

#2759

World Rank

#2883

Historical Rank

computer-science Degrees

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.

(See a Problem?)

Santosh Vempala's Published Works

Number of citations in a given year to any of this author's works

Total number of citations to an author for the works they published in a given year. This highlights publication of the most important work(s) by the author

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: