2009 |
100 | EE | Navin Goyal,
Luis Rademacher,
Santosh Vempala:
Expanders via random spanning trees.
SODA 2009: 576-585 |
99 | EE | Karthekeyan Chandrasekaran,
Daniel Dadush,
Santosh Vempala:
Thin Partitions: Isoperimetric Inequalities and Sampling Algorithms for some Nonconvex Families
CoRR abs/0904.0583: (2009) |
2008 |
98 | EE | S. Charles Brubaker,
Santosh Vempala:
Isotropic PCA and Affine-Invariant Clustering.
FOCS 2008: 551-560 |
97 | EE | Murtaza Motiwala,
Megan Elmore,
Nick Feamster,
Santosh Vempala:
Path splicing.
SIGCOMM 2008: 27-38 |
96 | EE | Maria-Florina Balcan,
Avrim Blum,
Santosh Vempala:
A discriminative framework for clustering via similarity functions.
STOC 2008: 671-680 |
95 | EE | Alan M. Frieze,
Santosh Vempala,
Juan Vera:
Logconcave random graphs.
STOC 2008: 779-788 |
94 | EE | S. Charles Brubaker,
Santosh Vempala:
Isotropic PCA and Affine-Invariant Clustering
CoRR abs/0804.3575: (2008) |
93 | EE | Navin Goyal,
Luis Rademacher,
Santosh Vempala:
Expanders via Random Spanning Trees
CoRR abs/0807.1496: (2008) |
92 | EE | John Dunagan,
Santosh Vempala:
A simple polynomial-time rescaling algorithm for solving linear programs.
Math. Program. 114(1): 101-114 (2008) |
91 | EE | Ravindran Kannan,
Hadi Salmasian,
Santosh Vempala:
The Spectral Method for General Mixture Models.
SIAM J. Comput. 38(3): 1141-1156 (2008) |
2007 |
90 | EE | Anirudh Ramachandran,
Nick Feamster,
Santosh Vempala:
Filtering spam with behavioral blacklisting.
ACM Conference on Computer and Communications Security 2007: 342-351 |
89 | EE | Santosh Vempala:
Spectral Algorithms for Learning and Clustering.
COLT 2007: 3-4 |
88 | EE | Alexandre Belloni,
Robert M. Freund,
Santosh Vempala:
An Efficient Re-scaled Perceptron Algorithm for Conic Systems.
COLT 2007: 393-408 |
87 | EE | Daniel Stefankovic,
Santosh Vempala,
Eric Vigoda:
Adaptive Simulated Annealing: A Near-optimal Connection between Sampling and Counting.
FOCS 2007: 183-193 |
86 | EE | László Lovász,
Santosh Vempala:
The geometry of logconcave functions and sampling algorithms.
Random Struct. Algorithms 30(3): 307-358 (2007) |
85 | EE | Imre Bárány,
Santosh Vempala,
Adrian Vetta:
Nash equilibria in random games.
Random Struct. Algorithms 31(4): 391-405 (2007) |
2006 |
84 | EE | Amit Deshpande,
Santosh Vempala:
Adaptive Sampling and Fast Low-Rank Matrix Approximation.
APPROX-RANDOM 2006: 292-303 |
83 | EE | László Lovász,
Santosh Vempala:
Fast Algorithms for Logconcave Functions: Sampling, Rounding, Integration and Optimization.
FOCS 2006: 57-68 |
82 | EE | Luis Rademacher,
Santosh Vempala:
Dispersion of Mass and the Complexity of Randomized Geometric Algorithms.
FOCS 2006: 729-738 |
81 | EE | Amit Deshpande,
Luis Rademacher,
Santosh Vempala,
Grant Wang:
Matrix approximation and projective clustering via volume sampling.
SODA 2006: 1117-1126 |
80 | EE | 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 |
79 | EE | David Pritchard,
Santosh Vempala:
Symmetric network computation.
SPAA 2006: 261-270 |
78 | EE | David Cheng,
Ravi Kannan,
Santosh Vempala,
Grant Wang:
A divide-and-merge methodology for clustering.
ACM Trans. Database Syst. 31(4): 1499-1525 (2006) |
77 | EE | Luis Rademacher,
Santosh Vempala:
Dispersion of Mass and the Complexity of Randomized Geometric Algorithms
CoRR abs/cs/0608054: (2006) |
76 | EE | Daniel Stefankovic,
Santosh Vempala,
Eric Vigoda:
Adaptive Simulated Annealing: A Near-optimal Connection between Sampling and Counting
CoRR abs/cs/0612058: (2006) |
75 | EE | Christos H. Papadimitriou,
Santosh Vempala:
On The Approximability Of The Traveling Salesman Problem.
Combinatorica 26(1): 101-120 (2006) |
74 | EE | Joseph Cheriyan,
Santosh Vempala,
Adrian Vetta:
Network Design Via Iterative Rounding Of Setpair Relaxations.
Combinatorica 26(3): 255-275 (2006) |
73 | EE | Amit Deshpande,
Santosh Vempala:
Adaptive Sampling and Fast Low-Rank Matrix Approximation.
Electronic Colloquium on Computational Complexity (ECCC) 13(042): (2006) |
72 | EE | Luis Rademacher,
Santosh Vempala:
Dispersion of Mass and the Complexity of Randomized Geometric Algorithms.
Electronic Colloquium on Computational Complexity (ECCC) 13(102): (2006) |
71 | EE | 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) |
70 | EE | Rosa I. Arriaga,
Santosh Vempala:
An algorithmic theory of learning: Robust concepts and random projection.
Machine Learning 63(2): 161-182 (2006) |
69 | EE | Maria-Florina Balcan,
Avrim Blum,
Santosh Vempala:
Kernels as features: On kernels, margins, and low-dimensional mappings.
Machine Learning 65(1): 79-94 (2006) |
68 | EE | László Lovász,
Santosh Vempala:
Hit-and-Run from a Corner.
SIAM J. Comput. 35(4): 985-1005 (2006) |
67 | EE | 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 | EE | Ravindran Kannan,
Hadi Salmasian,
Santosh Vempala:
The Spectral Method for General Mixture Models.
COLT 2005: 444-457 |
65 | EE | Imre Bárány,
Santosh Vempala,
Adrian Vetta:
Nash Equilibria in Random Games.
FOCS 2005: 123-131 |
64 | EE | David Cheng,
Santosh Vempala,
Ravi Kannan,
Grant Wang:
A divide-and-merge methodology for clustering.
PODS 2005: 196-205 |
63 | EE | 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 | EE | Adam Tauman Kalai,
Santosh Vempala:
Efficient algorithms for online decision problems.
J. Comput. Syst. Sci. 71(3): 291-307 (2005) |
2004 |
61 | EE | Maria-Florina Balcan,
Avrim Blum,
Santosh Vempala:
On Kernels, Margins, and Low-Dimensional Mappings.
ALT 2004: 194-205 |
60 | EE | Luis Rademacher,
Santosh Vempala:
Testing Geometric Convexity.
FSTTCS 2004: 469-480 |
59 | EE | László Lovász,
Santosh Vempala:
Hit-and-run from a corner.
STOC 2004: 310-314 |
58 | EE | John Dunagan,
Santosh Vempala:
A simple polynomial-time rescaling algorithm for solving linear programs.
STOC 2004: 315-320 |
57 | EE | Hadi Salmasian,
Ravindran Kannan,
Santosh Vempala:
The Spectral Method for Mixture Models
Electronic Colloquium on Computational Complexity (ECCC)(067): (2004) |
56 | EE | Ravi Kannan,
Santosh Vempala,
Adrian Vetta:
On clusterings: Good, bad and spectral.
J. ACM 51(3): 497-515 (2004) |
55 | EE | Dimitris Bertsimas,
Santosh Vempala:
Solving convex programs by random walks.
J. ACM 51(4): 540-556 (2004) |
54 | EE | Alan M. Frieze,
Ravi Kannan,
Santosh Vempala:
Fast monte-carlo algorithms for finding low-rank approximations.
J. ACM 51(6): 1025-1041 (2004) |
53 | EE | John Dunagan,
Santosh Vempala:
Optimal outlier removal in high-dimensional spaces.
J. Comput. Syst. Sci. 68(2): 335-373 (2004) |
52 | EE | Santosh Vempala,
Grant Wang:
A spectral algorithm for learning mixture models.
J. Comput. Syst. Sci. 68(4): 841-860 (2004) |
51 | EE | 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 | EE | 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 | EE | Claudson F. Bornstein,
Santosh Vempala:
Flow metrics.
Theor. Comput. Sci. 321(1): 13-24 (2004) |
2003 |
48 | EE | Adam Kalai,
Santosh Vempala:
Efficient Algorithms for Online Decision Problems.
COLT 2003: 26-40 |
47 | EE | László Lovász,
Santosh Vempala:
Logconcave Functions: Geometry and Efficient Sampling Algorithms
FOCS 2003: 640-649 |
46 | EE | László Lovász,
Santosh Vempala:
Simulated Annealing in Convex Bodies and an 0*(n4) Volume Algorithm.
FOCS 2003: 650- |
45 | EE | 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 | EE | Santosh Vempala,
Grant Wang:
A Spectral Algorithm for Learning Mixtures of Distributions.
FOCS 2002: 113- |
43 | EE | Claudson F. Bornstein,
Santosh Vempala:
Flow Metrics.
LATIN 2002: 516-527 |
42 | EE | Dimitris Bertsimas,
Santosh Vempala:
Solving convex programs by random walks.
STOC 2002: 109-115 |
41 | EE | Joseph Cheriyan,
Santosh Vempala,
Adrian Vetta:
Approximation algorithms for minimum-cost k-vertex connected subgraphs.
STOC 2002: 306-312 |
40 | EE | Adam Kalai,
Santosh Vempala:
Efficient Algorithms for Universal Portfolios.
Journal of Machine Learning Research 3: 423-440 (2002) |
39 | EE | Robert D. Carr,
Santosh Vempala:
Randomized metarounding.
Random Struct. Algorithms 20(3): 343-352 (2002) |
2001 |
38 | EE | Joseph Cheriyan,
Santosh Vempala:
Edge Covers of Setpairs and the Iterative Rounding Method.
IPCO 2001: 30-44 |
37 | EE | Alantha Newman,
Santosh Vempala:
Fences Are Futile: On Relaxations for the Linear Ordering Problem.
IPCO 2001: 333-347 |
36 | EE | John Dunagan,
Santosh Vempala:
On Euclidean Embeddings and Bandwidth Minimization.
RANDOM-APPROX 2001: 229-240 |
35 | EE | John Dunagan,
Santosh Vempala:
Optimal outlier removal in high-dimensional.
STOC 2001: 627-636 |
34 | EE | Prasad Tetali,
Santosh Vempala:
Random Sampling of Euler Tours.
Algorithmica 30(3): 376-385 (2001) |
2000 |
33 | EE | 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 | EE | Robert D. Carr,
Santosh Vempala,
Jacques Mandler:
Towards a 4/3 approximation for the asymmetric traveling salesman problem.
SODA 2000: 116-125 |
29 | EE | Christos H. Papadimitriou,
Santosh Vempala:
On the approximability of the traveling salesman problem (extended abstract).
STOC 2000: 126-133 |
28 | EE | 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 | EE | 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 | EE | Rosa I. Arriaga,
Santosh Vempala:
An Algorithmic Theory of Learning: Robust Concepts and Random Projection.
FOCS 1999: 616-623 |
24 | EE | Santosh Vempala,
Berthold Vöcking:
Approximating Multicast Congestion.
ISAAC 1999: 367-372 |
23 | EE | Petros Drineas,
Alan M. Frieze,
Ravi Kannan,
Santosh Vempala,
V. Vinay:
Clustering in Large Graphs and Matrices.
SODA 1999: 291-299 |
22 | EE | 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 | EE | Alan M. Frieze,
Ravi Kannan,
Santosh Vempala:
Fast Monte-Carlo Algorithms for Finding Low-Rank Approximations.
FOCS 1998: 370-378 |
18 | EE | Santosh Vempala:
Random Projection: A New Approach to VLSI Layout.
FOCS 1998: 389-395 |
17 | EE | Christos H. Papadimitriou,
Prabhakar Raghavan,
Hisao Tamaki,
Santosh Vempala:
Latent Semantic Indexing: A Probabilistic Analysis.
PODS 1998: 159-168 |
16 | EE | 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 | EE | 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 | EE | Piotr Indyk,
Rajeev Motwani,
Prabhakar Raghavan,
Santosh Vempala:
Locality-Preserving Hashing in Multidimensional Spaces.
STOC 1997: 618-625 |
8 | EE | 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 | EE | Avrim Blum,
R. Ravi,
Santosh Vempala:
A Constant-factor Approximation Algorithm for the k MST Problem (Extended Abstract).
STOC 1996: 442-448 |
1995 |
4 | EE | 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 | EE | 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 |