 | 2009 |
|---|
| 108 |       | S. Charles Brubaker,
Santosh Vempala:
Random Tensors and Planted Cliques.
APPROX-RANDOM 2009: 406-419 |
| 107 | | Karthekeyan Chandrasekaran,
Amit Deshpande,
Santosh Vempala:
Sampling s-Concave Functions: The Limit of Convexity Based Isoperimetry.
APPROX-RANDOM 2009: 420-433 |
| 106 | | Navin Goyal,
Luis Rademacher,
Santosh Vempala:
Expanders via random spanning trees.
SODA 2009: 576-585 |
| 105 | | Karthekeyan Chandrasekaran,
Daniel Dadush,
Santosh Vempala:
Thin Partitions: Isoperimetric Inequalities and Sampling Algorithms for some Nonconvex Families
CoRR abs/0904.0583: (2009) |
| 104 | | S. Charles Brubaker,
Santosh Vempala:
Random Tensors and Planted Cliques
CoRR abs/0905.2381: (2009) |
| 103 | | Karthekeyan Chandrasekaran,
Amit Deshpande,
Santosh Vempala:
The Limit of Convexity Based Isoperimetry: Sampling Harmonic-Concave Functions
CoRR abs/0906.2448: (2009) |
| 102 | | Ravi Kannan,
Santosh Vempala:
Spectral Algorithms.
Foundations and Trends in Theoretical Computer Science 4(3-4): 157-288 (2009) |
| 101 | | Daniel Stefankovic,
Santosh Vempala,
Eric Vigoda:
Adaptive simulated annealing: A near-optimal connection between sampling and counting.
J. ACM 56(3): (2009) |
| 2008 |
|---|
| 100 | | S. Charles Brubaker,
Santosh Vempala:
Isotropic PCA and Affine-Invariant Clustering.
FOCS 2008: 551-560 |
| 99 | | Murtaza Motiwala,
Megan Elmore,
Nick Feamster,
Santosh Vempala:
Path splicing.
SIGCOMM 2008: 27-38 |
| 98 | | Maria-Florina Balcan,
Avrim Blum,
Santosh Vempala:
A discriminative framework for clustering via similarity functions.
STOC 2008: 671-680 |
| 97 | | Alan M. Frieze,
Santosh Vempala,
Juan Vera:
Logconcave random graphs.
STOC 2008: 779-788 |
| 96 | | S. Charles Brubaker,
Santosh Vempala:
Isotropic PCA and Affine-Invariant Clustering
CoRR abs/0804.3575: (2008) |
| 95 | | Navin Goyal,
Luis Rademacher,
Santosh Vempala:
Expanders via Random Spanning Trees
CoRR abs/0807.1496: (2008) |
| 94 | | John Dunagan,
Santosh Vempala:
A simple polynomial-time rescaling algorithm for solving linear programs.
Math. Program. 114(1): 101-114 (2008) |
| 93 | | Dimitris Bertsimas,
Margrét V. Bjarnadóttir,
Michael A. Kane,
J. Christian Kryder,
Rudra Pandey,
Santosh Vempala,
Grant Wang:
Algorithmic Prediction of Health-Care Costs.
Operations Research 56(6): 1382-1392 (2008) |
| 92 | | Ravindran Kannan,
Hadi Salmasian,
Santosh Vempala:
The Spectral Method for General Mixture Models.
SIAM J. Comput. 38(3): 1141-1156 (2008) |
| 2007 |
|---|
| 91 | | Anirudh Ramachandran,
Nick Feamster,
Santosh Vempala:
Filtering spam with behavioral blacklisting.
ACM Conference on Computer and Communications Security 2007: 342-351 |
| 90 | | Santosh Vempala:
Spectral Algorithms for Learning and Clustering.
COLT 2007: 3-4 |
| 89 | | Alexandre Belloni,
Robert M. Freund,
Santosh Vempala:
An Efficient Re-scaled Perceptron Algorithm for Conic Systems.
COLT 2007: 393-408 |
| 88 | | Daniel Stefankovic,
Santosh Vempala,
Eric Vigoda:
Adaptive Simulated Annealing: A Near-optimal Connection between Sampling and Counting.
FOCS 2007: 183-193 |
| 87 | | László Lovász,
Santosh Vempala:
The geometry of logconcave functions and sampling algorithms.
Random Struct. Algorithms 30(3): 307-358 (2007) |
| 86 | | Imre Bárány,
Santosh Vempala,
Adrian Vetta:
Nash equilibria in random games.
Random Struct. Algorithms 31(4): 391-405 (2007) |
| 2006 |
|---|
| 85 | | Amit Deshpande,
Santosh Vempala:
Adaptive Sampling and Fast Low-Rank Matrix Approximation.
APPROX-RANDOM 2006: 292-303 |
| 84 | | László Lovász,
Santosh Vempala:
Fast Algorithms for Logconcave Functions: Sampling, Rounding, Integration and Optimization.
FOCS 2006: 57-68 |
| 83 | | Luis Rademacher,
Santosh Vempala:
Dispersion of Mass and the Complexity of Randomized Geometric Algorithms.
FOCS 2006: 729-738 |
| 82 | | Amit Deshpande,
Luis Rademacher,
Santosh Vempala,
Grant Wang:
Matrix approximation and projective clustering via volume sampling.
SODA 2006: 1117-1126 |
| 81 | | Sanjeev Arora,
László Lovász,
Ilan Newman,
Yuval Rabani,
Yuri Rabinovich,
Santosh Vempala:
Local versus global properties of metric spaces.
SODA 2006: 41-50 |
| 80 | | David Pritchard,
Santosh Vempala:
Symmetric network computation.
SPAA 2006: 261-270 |
| 79 | | David Cheng,
Ravi Kannan,
Santosh Vempala,
Grant Wang:
A divide-and-merge methodology for clustering.
ACM Trans. Database Syst. 31(4): 1499-1525 (2006) |
| 78 | | Luis Rademacher,
Santosh Vempala:
Dispersion of Mass and the Complexity of Randomized Geometric Algorithms
CoRR abs/cs/0608054: (2006) |
| 77 | | Daniel Stefankovic,
Santosh Vempala,
Eric Vigoda:
Adaptive Simulated Annealing: A Near-optimal Connection between Sampling and Counting
CoRR abs/cs/0612058: (2006) |
| 76 | | Christos H. Papadimitriou,
Santosh Vempala:
On The Approximability Of The Traveling Salesman Problem.
Combinatorica 26(1): 101-120 (2006) |
| 75 | | Joseph Cheriyan,
Santosh Vempala,
Adrian Vetta:
Network Design Via Iterative Rounding Of Setpair Relaxations.
Combinatorica 26(3): 255-275 (2006) |
| 74 | | Amit Deshpande,
Santosh Vempala:
Adaptive Sampling and Fast Low-Rank Matrix Approximation.
Electronic Colloquium on Computational Complexity (ECCC) 13(042): (2006) |
| 73 | | Luis Rademacher,
Santosh Vempala:
Dispersion of Mass and the Complexity of Randomized Geometric Algorithms.
Electronic Colloquium on Computational Complexity (ECCC) 13(102): (2006) |
| 72 | | László Lovász,
Santosh Vempala:
Simulated annealing in convex bodies and an O*(n4) volume algorithm.
J. Comput. Syst. Sci. 72(2): 392-417 (2006) |
| 71 | | Rosa I. Arriaga,
Santosh Vempala:
An algorithmic theory of learning: Robust concepts and random projection.
Machine Learning 63(2): 161-182 (2006) |
| 70 | | Maria-Florina Balcan,
Avrim Blum,
Santosh Vempala:
Kernels as features: On kernels, margins, and low-dimensional mappings.
Machine Learning 65(1): 79-94 (2006) |
| 69 | | Adam Tauman Kalai,
Santosh Vempala:
Simulated Annealing for Convex Optimization.
Math. Oper. Res. 31(2): 253-266 (2006) |
| 68 | | László Lovász,
Santosh Vempala:
Hit-and-Run from a Corner.
SIAM J. Comput. 35(4): 985-1005 (2006) |
| 67 | | Amit Deshpande,
Luis Rademacher,
Santosh Vempala,
Grant Wang:
Matrix Approximation and Projective Clustering via Volume Sampling.
Theory of Computing 2(1): 225-247 (2006) |
| 2005 |
|---|
| 66 | | Ravindran Kannan,
Hadi Salmasian,
Santosh Vempala:
The Spectral Method for General Mixture Models.
COLT 2005: 444-457 |
| 65 | | Imre Bárány,
Santosh Vempala,
Adrian Vetta:
Nash Equilibria in Random Games.
FOCS 2005: 123-131 |
| 64 | | David Cheng,
Santosh Vempala,
Ravi Kannan,
Grant Wang:
A divide-and-merge methodology for clustering.
PODS 2005: 196-205 |
| 63 | | Wenceslas Fernandez de la Vega,
Marek Karpinski,
Ravi Kannan,
Santosh Vempala:
Tensor decomposition and approximation schemes for constraint satisfaction problems.
STOC 2005: 747-754 |
| 62 | | Adam Tauman Kalai,
Santosh Vempala:
Efficient algorithms for online decision problems.
J. Comput. Syst. Sci. 71(3): 291-307 (2005) |
| 2004 |
|---|
| 61 | | Maria-Florina Balcan,
Avrim Blum,
Santosh Vempala:
On Kernels, Margins, and Low-Dimensional Mappings.
ALT 2004: 194-205 |
| 60 | | Luis Rademacher,
Santosh Vempala:
Testing Geometric Convexity.
FSTTCS 2004: 469-480 |
| 59 | | László Lovász,
Santosh Vempala:
Hit-and-run from a corner.
STOC 2004: 310-314 |
| 58 | | John Dunagan,
Santosh Vempala:
A simple polynomial-time rescaling algorithm for solving linear programs.
STOC 2004: 315-320 |
| 57 | | Hadi Salmasian,
Ravindran Kannan,
Santosh Vempala:
The Spectral Method for Mixture Models
Electronic Colloquium on Computational Complexity (ECCC)(067): (2004) |
| 56 | | Ravi Kannan,
Santosh Vempala,
Adrian Vetta:
On clusterings: Good, bad and spectral.
J. ACM 51(3): 497-515 (2004) |
| 55 | | Dimitris Bertsimas,
Santosh Vempala:
Solving convex programs by random walks.
J. ACM 51(4): 540-556 (2004) |
| 54 | | Alan M. Frieze,
Ravi Kannan,
Santosh Vempala:
Fast monte-carlo algorithms for finding low-rank approximations.
J. ACM 51(6): 1025-1041 (2004) |
| 53 | | John Dunagan,
Santosh Vempala:
Optimal outlier removal in high-dimensional spaces.
J. Comput. Syst. Sci. 68(2): 335-373 (2004) |
| 52 | | Santosh Vempala,
Grant Wang:
A spectral algorithm for learning mixture models.
J. Comput. Syst. Sci. 68(4): 841-860 (2004) |
| 51 | | Petros Drineas,
Alan M. Frieze,
Ravi Kannan,
Santosh Vempala,
V. Vinay:
Clustering Large Graphs via the Singular Value Decomposition.
Machine Learning 56(1-3): 9-33 (2004) |
| 50 | | Robert D. Carr,
Santosh Vempala:
On the Held-Karp relaxation for the asymmetric and symmetric traveling salesman problems.
Math. Program. 100(3): 569-587 (2004) |
| 49 | | Claudson F. Bornstein,
Santosh Vempala:
Flow metrics.
Theor. Comput. Sci. 321(1): 13-24 (2004) |
| 2003 |
|---|
| 48 | | Adam Kalai,
Santosh Vempala:
Efficient Algorithms for Online Decision Problems.
COLT 2003: 26-40 |
| 47 | | László Lovász,
Santosh Vempala:
Logconcave Functions: Geometry and Efficient Sampling Algorithms
FOCS 2003: 640-649 |
| 46 | | László Lovász,
Santosh Vempala:
Simulated Annealing in Convex Bodies and an 0*(n4) Volume Algorithm.
FOCS 2003: 650- |
| 45 | | Joseph Cheriyan,
Santosh Vempala,
Adrian Vetta:
An Approximation Algorithm for the Minimum-Cost k-Vertex Connected Subgraph.
SIAM J. Comput. 32(4): 1050-1055 (2003) |
| 2002 |
|---|
| 44 | | Santosh Vempala,
Grant Wang:
A Spectral Algorithm for Learning Mixtures of Distributions.
FOCS 2002: 113- |
| 43 | | Claudson F. Bornstein,
Santosh Vempala:
Flow Metrics.
LATIN 2002: 516-527 |
| 42 | | Dimitris Bertsimas,
Santosh Vempala:
Solving convex programs by random walks.
STOC 2002: 109-115 |
| 41 | | Joseph Cheriyan,
Santosh Vempala,
Adrian Vetta:
Approximation algorithms for minimum-cost k-vertex connected subgraphs.
STOC 2002: 306-312 |
| 40 | | Adam Kalai,
Santosh Vempala:
Efficient Algorithms for Universal Portfolios.
Journal of Machine Learning Research 3: 423-440 (2002) |
| 39 | | Robert D. Carr,
Santosh Vempala:
Randomized metarounding.
Random Struct. Algorithms 20(3): 343-352 (2002) |
| 2001 |
|---|
| 38 | | Joseph Cheriyan,
Santosh Vempala:
Edge Covers of Setpairs and the Iterative Rounding Method.
IPCO 2001: 30-44 |
| 37 | | Alantha Newman,
Santosh Vempala:
Fences Are Futile: On Relaxations for the Linear Ordering Problem.
IPCO 2001: 333-347 |
| 36 | | John Dunagan,
Santosh Vempala:
On Euclidean Embeddings and Bandwidth Minimization.
RANDOM-APPROX 2001: 229-240 |
| 35 | | John Dunagan,
Santosh Vempala:
Optimal outlier removal in high-dimensional.
STOC 2001: 627-636 |
| 34 | | Prasad Tetali,
Santosh Vempala:
Random Sampling of Euler Tours.
Algorithmica 30(3): 376-385 (2001) |
| 2000 |
|---|
| 33 | | Santosh Vempala,
Adrian Vetta:
Factor 4/3 approximations for minimum 2-connected subgraphs.
APPROX 2000: 262-273 |
| 32 |  | Ravi Kannan,
Santosh Vempala,
Adrian Vetta:
On Clusterings - Good, Bad and Spectral.
FOCS 2000: 367-377 |
| 31 | | Adam Kalai,
Santosh Vempala:
Efficient Algorithms for Universal Portfolios.
FOCS 2000: 486-491 |
| 30 | | Robert D. Carr,
Santosh Vempala,
Jacques Mandler:
Towards a 4/3 approximation for the asymmetric traveling salesman problem.
SODA 2000: 116-125 |
| 29 | | Christos H. Papadimitriou,
Santosh Vempala:
On the approximability of the traveling salesman problem (extended abstract).
STOC 2000: 126-133 |
| 28 | | Robert D. Carr,
Santosh Vempala:
Randomized metarounding (extended abstract).
STOC 2000: 58-62 |
| 27 | | Christos H. Papadimitriou,
Prabhakar Raghavan,
Hisao Tamaki,
Santosh Vempala:
Latent Semantic Indexing: A Probabilistic Analysis.
J. Comput. Syst. Sci. 61(2): 217-235 (2000) |
| 26 | | Avrim Blum,
Goran Konjevod,
R. Ravi,
Santosh Vempala:
Semi-definite relaxations for minimum bandwidth and other vertex-ordering problems.
Theor. Comput. Sci. 235(1): 25-42 (2000) |
| 1999 |
|---|
| 25 | | Rosa I. Arriaga,
Santosh Vempala:
An Algorithmic Theory of Learning: Robust Concepts and Random Projection.
FOCS 1999: 616-623 |
| 24 | | Santosh Vempala,
Berthold Vöcking:
Approximating Multicast Congestion.
ISAAC 1999: 367-372 |
| 23 | | Petros Drineas,
Alan M. Frieze,
Ravi Kannan,
Santosh Vempala,
V. Vinay:
Clustering in Large Graphs and Matrices.
SODA 1999: 291-299 |
| 22 | | Santosh Vempala,
Mihalis Yannakakis:
A Convex Relaxation for the Asymmetric TSP.
SODA 1999: 975-976 |
| 21 | | Avrim Blum,
R. Ravi,
Santosh Vempala:
A Constant-Factor Approximation Algorithm for the k-MST Problem.
J. Comput. Syst. Sci. 58(1): 101-108 (1999) |
| 20 | | Ravi Kannan,
Prasad Tetali,
Santosh Vempala:
Simple Markov-chain algorithms for generating bipartite graphs and tournaments.
Random Struct. Algorithms 14(4): 293-308 (1999) |
| 1998 |
|---|
| 19 | | Alan M. Frieze,
Ravi Kannan,
Santosh Vempala:
Fast Monte-Carlo Algorithms for Finding Low-Rank Approximations.
FOCS 1998: 370-378 |
| 18 | | Santosh Vempala:
Random Projection: A New Approach to VLSI Layout.
FOCS 1998: 389-395 |
| 17 | | Christos H. Papadimitriou,
Prabhakar Raghavan,
Hisao Tamaki,
Santosh Vempala:
Latent Semantic Indexing: A Probabilistic Analysis.
PODS 1998: 159-168 |
| 16 | | Avrim Blum,
Goran Konjevod,
R. Ravi,
Santosh Vempala:
Semi-Definite Relaxations for Minimum Bandwidth and other Vertex-Ordering Problems.
STOC 1998: 100-105 |
| 15 | | Avrim Blum,
Alan M. Frieze,
Ravi Kannan,
Santosh Vempala:
A Polynomial-Time Algorithm for Learning Noisy Linear Threshold Functions.
Algorithmica 22(1/2): 35-52 (1998) |
| 14 | | Baruch Awerbuch,
Yossi Azar,
Avrim Blum,
Santosh Vempala:
New Approximation Guarantees for Minimum-Weight k-Trees and Prize-Collecting Salesmen.
SIAM J. Comput. 28(1): 254-262 (1998) |
| 13 | | Joseph S. B. Mitchell,
Avrim Blum,
Prasad Chalasani,
Santosh Vempala:
A Constant-Factor Approximation Algorithm for the Geometric k-MST Problem in the Plane.
SIAM J. Comput. 28(3): 771-781 (1998) |
| 1997 |
|---|
| 12 | | Santosh Vempala:
A Random Sampling Based Algorithm for Learning the Intersection of Half-spaces.
FOCS 1997: 508-513 |
| 11 | | Prasad Tetali,
Santosh Vempala:
Random Sampling of Euler Tours.
RANDOM 1997: 57-66 |
| 10 | | Ravi Kannan,
Prasad Tetali,
Santosh Vempala:
Simple Markov-Chain Algorithms for Generating Bipartite Graphs and Tournaments (Extended Abstract).
SODA 1997: 193-200 |
| 9 | | Piotr Indyk,
Rajeev Motwani,
Prabhakar Raghavan,
Santosh Vempala:
Locality-Preserving Hashing in Multidimensional Spaces.
STOC 1997: 618-625 |
| 8 | | Ravi Kannan,
Santosh Vempala:
Sampling Lattice Points.
STOC 1997: 696-700 |
| 7 | | Andrew Kotlov,
László Lovász,
Santosh Vempala:
The Colin de Verdière Number and Sphere Representations of a Graph.
Combinatorica 17(4): 483-521 (1997) |
| 1996 |
|---|
| 6 | | Avrim Blum,
Alan M. Frieze,
Ravi Kannan,
Santosh Vempala:
A Polynomial-Time Algorithm for Learning Noisy Linear Threshold Functions.
FOCS 1996: 330-338 |
| 5 | | Avrim Blum,
R. Ravi,
Santosh Vempala:
A Constant-factor Approximation Algorithm for the k MST Problem (Extended Abstract).
STOC 1996: 442-448 |
| 1995 |
|---|
| 4 | | Baruch Awerbuch,
Yossi Azar,
Avrim Blum,
Santosh Vempala:
Improved approximation guarantees for minimum-weight k-trees and prize-collecting salesmen.
STOC 1995: 277-283 |
| 3 | | Avrim Blum,
Prasad Chalasani,
Santosh Vempala:
A constant-factor approximation for the k-MST problem in the plane.
STOC 1995: 294-302 |
| 1994 |
|---|
| 2 | | Vivek Arora,
Santosh Vempala,
Huzur Saran,
Vijay V. Vazirani:
A Limited-Backtrack Greedy Schema for Approximation Algorithms.
FSTTCS 1994: 318-329 |
| 1993 |
|---|
| 1 | | Naveen Garg,
Santosh Vempala,
Aman Singla:
Improved Approximation Algorithms for Biconnected Subgraphs via Better Lower Bounding Techniques.
SODA 1993: 103-111 |
