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 |