dblp.uni-trier.dewww.uni-trier.de

Santosh Vempala Vis

List of publications from the DBLP Bibliography Server - FAQ
Coauthor Index - Ask others: ACM DL/Guide - CiteSeerX - CSB - MetaPress - Google - Bing - Yahoo
Home Page

*2009
108EES. Charles Brubaker, Santosh Vempala: Random Tensors and Planted Cliques. APPROX-RANDOM 2009: 406-419
107EEKarthekeyan Chandrasekaran, Amit Deshpande, Santosh Vempala: Sampling s-Concave Functions: The Limit of Convexity Based Isoperimetry. APPROX-RANDOM 2009: 420-433
106EENavin Goyal, Luis Rademacher, Santosh Vempala: Expanders via random spanning trees. SODA 2009: 576-585
105EEKarthekeyan Chandrasekaran, Daniel Dadush, Santosh Vempala: Thin Partitions: Isoperimetric Inequalities and Sampling Algorithms for some Nonconvex Families CoRR abs/0904.0583: (2009)
104EES. Charles Brubaker, Santosh Vempala: Random Tensors and Planted Cliques CoRR abs/0905.2381: (2009)
103EEKarthekeyan Chandrasekaran, Amit Deshpande, Santosh Vempala: The Limit of Convexity Based Isoperimetry: Sampling Harmonic-Concave Functions CoRR abs/0906.2448: (2009)
102EERavi Kannan, Santosh Vempala: Spectral Algorithms. Foundations and Trends in Theoretical Computer Science 4(3-4): 157-288 (2009)
101EEDaniel Stefankovic, Santosh Vempala, Eric Vigoda: Adaptive simulated annealing: A near-optimal connection between sampling and counting. J. ACM 56(3): (2009)
2008
100EES. Charles Brubaker, Santosh Vempala: Isotropic PCA and Affine-Invariant Clustering. FOCS 2008: 551-560
99EEMurtaza Motiwala, Megan Elmore, Nick Feamster, Santosh Vempala: Path splicing. SIGCOMM 2008: 27-38
98EEMaria-Florina Balcan, Avrim Blum, Santosh Vempala: A discriminative framework for clustering via similarity functions. STOC 2008: 671-680
97EEAlan M. Frieze, Santosh Vempala, Juan Vera: Logconcave random graphs. STOC 2008: 779-788
96EES. Charles Brubaker, Santosh Vempala: Isotropic PCA and Affine-Invariant Clustering CoRR abs/0804.3575: (2008)
95EENavin Goyal, Luis Rademacher, Santosh Vempala: Expanders via Random Spanning Trees CoRR abs/0807.1496: (2008)
94EEJohn Dunagan, Santosh Vempala: A simple polynomial-time rescaling algorithm for solving linear programs. Math. Program. 114(1): 101-114 (2008)
93EEDimitris 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)
92EERavindran Kannan, Hadi Salmasian, Santosh Vempala: The Spectral Method for General Mixture Models. SIAM J. Comput. 38(3): 1141-1156 (2008)
2007
91EEAnirudh Ramachandran, Nick Feamster, Santosh Vempala: Filtering spam with behavioral blacklisting. ACM Conference on Computer and Communications Security 2007: 342-351
90EESantosh Vempala: Spectral Algorithms for Learning and Clustering. COLT 2007: 3-4
89EEAlexandre Belloni, Robert M. Freund, Santosh Vempala: An Efficient Re-scaled Perceptron Algorithm for Conic Systems. COLT 2007: 393-408
88EEDaniel Stefankovic, Santosh Vempala, Eric Vigoda: Adaptive Simulated Annealing: A Near-optimal Connection between Sampling and Counting. FOCS 2007: 183-193
87EELászló Lovász, Santosh Vempala: The geometry of logconcave functions and sampling algorithms. Random Struct. Algorithms 30(3): 307-358 (2007)
86EEImre Bárány, Santosh Vempala, Adrian Vetta: Nash equilibria in random games. Random Struct. Algorithms 31(4): 391-405 (2007)
2006
85EEAmit Deshpande, Santosh Vempala: Adaptive Sampling and Fast Low-Rank Matrix Approximation. APPROX-RANDOM 2006: 292-303
84EELászló Lovász, Santosh Vempala: Fast Algorithms for Logconcave Functions: Sampling, Rounding, Integration and Optimization. FOCS 2006: 57-68
83EELuis Rademacher, Santosh Vempala: Dispersion of Mass and the Complexity of Randomized Geometric Algorithms. FOCS 2006: 729-738
82EEAmit Deshpande, Luis Rademacher, Santosh Vempala, Grant Wang: Matrix approximation and projective clustering via volume sampling. SODA 2006: 1117-1126
81EESanjeev Arora, László Lovász, Ilan Newman, Yuval Rabani, Yuri Rabinovich, Santosh Vempala: Local versus global properties of metric spaces. SODA 2006: 41-50
80EEDavid Pritchard, Santosh Vempala: Symmetric network computation. SPAA 2006: 261-270
79EEDavid Cheng, Ravi Kannan, Santosh Vempala, Grant Wang: A divide-and-merge methodology for clustering. ACM Trans. Database Syst. 31(4): 1499-1525 (2006)
78EELuis Rademacher, Santosh Vempala: Dispersion of Mass and the Complexity of Randomized Geometric Algorithms CoRR abs/cs/0608054: (2006)
77EEDaniel Stefankovic, Santosh Vempala, Eric Vigoda: Adaptive Simulated Annealing: A Near-optimal Connection between Sampling and Counting CoRR abs/cs/0612058: (2006)
76EEChristos H. Papadimitriou, Santosh Vempala: On The Approximability Of The Traveling Salesman Problem. Combinatorica 26(1): 101-120 (2006)
75EEJoseph Cheriyan, Santosh Vempala, Adrian Vetta: Network Design Via Iterative Rounding Of Setpair Relaxations. Combinatorica 26(3): 255-275 (2006)
74EEAmit Deshpande, Santosh Vempala: Adaptive Sampling and Fast Low-Rank Matrix Approximation. Electronic Colloquium on Computational Complexity (ECCC) 13(042): (2006)
73EELuis Rademacher, Santosh Vempala: Dispersion of Mass and the Complexity of Randomized Geometric Algorithms. Electronic Colloquium on Computational Complexity (ECCC) 13(102): (2006)
72EELá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)
71EERosa I. Arriaga, Santosh Vempala: An algorithmic theory of learning: Robust concepts and random projection. Machine Learning 63(2): 161-182 (2006)
70EEMaria-Florina Balcan, Avrim Blum, Santosh Vempala: Kernels as features: On kernels, margins, and low-dimensional mappings. Machine Learning 65(1): 79-94 (2006)
69EEAdam Tauman Kalai, Santosh Vempala: Simulated Annealing for Convex Optimization. Math. Oper. Res. 31(2): 253-266 (2006)
68EELászló Lovász, Santosh Vempala: Hit-and-Run from a Corner. SIAM J. Comput. 35(4): 985-1005 (2006)
67EEAmit Deshpande, Luis Rademacher, Santosh Vempala, Grant Wang: Matrix Approximation and Projective Clustering via Volume Sampling. Theory of Computing 2(1): 225-247 (2006)
2005
66EERavindran Kannan, Hadi Salmasian, Santosh Vempala: The Spectral Method for General Mixture Models. COLT 2005: 444-457
65EEImre Bárány, Santosh Vempala, Adrian Vetta: Nash Equilibria in Random Games. FOCS 2005: 123-131
64EEDavid Cheng, Santosh Vempala, Ravi Kannan, Grant Wang: A divide-and-merge methodology for clustering. PODS 2005: 196-205
63EEWenceslas Fernandez de la Vega, Marek Karpinski, Ravi Kannan, Santosh Vempala: Tensor decomposition and approximation schemes for constraint satisfaction problems. STOC 2005: 747-754
62EEAdam Tauman Kalai, Santosh Vempala: Efficient algorithms for online decision problems. J. Comput. Syst. Sci. 71(3): 291-307 (2005)
2004
61EEMaria-Florina Balcan, Avrim Blum, Santosh Vempala: On Kernels, Margins, and Low-Dimensional Mappings. ALT 2004: 194-205
60EELuis Rademacher, Santosh Vempala: Testing Geometric Convexity. FSTTCS 2004: 469-480
59EELászló Lovász, Santosh Vempala: Hit-and-run from a corner. STOC 2004: 310-314
58EEJohn Dunagan, Santosh Vempala: A simple polynomial-time rescaling algorithm for solving linear programs. STOC 2004: 315-320
57EEHadi Salmasian, Ravindran Kannan, Santosh Vempala: The Spectral Method for Mixture Models Electronic Colloquium on Computational Complexity (ECCC)(067): (2004)
56EERavi Kannan, Santosh Vempala, Adrian Vetta: On clusterings: Good, bad and spectral. J. ACM 51(3): 497-515 (2004)
55EEDimitris Bertsimas, Santosh Vempala: Solving convex programs by random walks. J. ACM 51(4): 540-556 (2004)
54EEAlan M. Frieze, Ravi Kannan, Santosh Vempala: Fast monte-carlo algorithms for finding low-rank approximations. J. ACM 51(6): 1025-1041 (2004)
53EEJohn Dunagan, Santosh Vempala: Optimal outlier removal in high-dimensional spaces. J. Comput. Syst. Sci. 68(2): 335-373 (2004)
52EESantosh Vempala, Grant Wang: A spectral algorithm for learning mixture models. J. Comput. Syst. Sci. 68(4): 841-860 (2004)
51EEPetros 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)
50EERobert D. Carr, Santosh Vempala: On the Held-Karp relaxation for the asymmetric and symmetric traveling salesman problems. Math. Program. 100(3): 569-587 (2004)
49EEClaudson F. Bornstein, Santosh Vempala: Flow metrics. Theor. Comput. Sci. 321(1): 13-24 (2004)
2003
48EEAdam Kalai, Santosh Vempala: Efficient Algorithms for Online Decision Problems. COLT 2003: 26-40
47EELászló Lovász, Santosh Vempala: Logconcave Functions: Geometry and Efficient Sampling Algorithms FOCS 2003: 640-649
46EELászló Lovász, Santosh Vempala: Simulated Annealing in Convex Bodies and an 0*(n4) Volume Algorithm. FOCS 2003: 650-
45EEJoseph 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
44EESantosh Vempala, Grant Wang: A Spectral Algorithm for Learning Mixtures of Distributions. FOCS 2002: 113-
43EEClaudson F. Bornstein, Santosh Vempala: Flow Metrics. LATIN 2002: 516-527
42EEDimitris Bertsimas, Santosh Vempala: Solving convex programs by random walks. STOC 2002: 109-115
41EEJoseph Cheriyan, Santosh Vempala, Adrian Vetta: Approximation algorithms for minimum-cost k-vertex connected subgraphs. STOC 2002: 306-312
40EEAdam Kalai, Santosh Vempala: Efficient Algorithms for Universal Portfolios. Journal of Machine Learning Research 3: 423-440 (2002)
39EERobert D. Carr, Santosh Vempala: Randomized metarounding. Random Struct. Algorithms 20(3): 343-352 (2002)
2001
38EEJoseph Cheriyan, Santosh Vempala: Edge Covers of Setpairs and the Iterative Rounding Method. IPCO 2001: 30-44
37EEAlantha Newman, Santosh Vempala: Fences Are Futile: On Relaxations for the Linear Ordering Problem. IPCO 2001: 333-347
36EEJohn Dunagan, Santosh Vempala: On Euclidean Embeddings and Bandwidth Minimization. RANDOM-APPROX 2001: 229-240
35EEJohn Dunagan, Santosh Vempala: Optimal outlier removal in high-dimensional. STOC 2001: 627-636
34EEPrasad Tetali, Santosh Vempala: Random Sampling of Euler Tours. Algorithmica 30(3): 376-385 (2001)
2000
33EESantosh 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
30EERobert D. Carr, Santosh Vempala, Jacques Mandler: Towards a 4/3 approximation for the asymmetric traveling salesman problem. SODA 2000: 116-125
29EEChristos H. Papadimitriou, Santosh Vempala: On the approximability of the traveling salesman problem (extended abstract). STOC 2000: 126-133
28EERobert 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)
26EEAvrim 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
25EERosa I. Arriaga, Santosh Vempala: An Algorithmic Theory of Learning: Robust Concepts and Random Projection. FOCS 1999: 616-623
24EESantosh Vempala, Berthold Vöcking: Approximating Multicast Congestion. ISAAC 1999: 367-372
23EEPetros Drineas, Alan M. Frieze, Ravi Kannan, Santosh Vempala, V. Vinay: Clustering in Large Graphs and Matrices. SODA 1999: 291-299
22EESantosh 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
19EEAlan M. Frieze, Ravi Kannan, Santosh Vempala: Fast Monte-Carlo Algorithms for Finding Low-Rank Approximations. FOCS 1998: 370-378
18EESantosh Vempala: Random Projection: A New Approach to VLSI Layout. FOCS 1998: 389-395
17EEChristos H. Papadimitriou, Prabhakar Raghavan, Hisao Tamaki, Santosh Vempala: Latent Semantic Indexing: A Probabilistic Analysis. PODS 1998: 159-168
16EEAvrim 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
12EESantosh 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
9EEPiotr Indyk, Rajeev Motwani, Prabhakar Raghavan, Santosh Vempala: Locality-Preserving Hashing in Multidimensional Spaces. STOC 1997: 618-625
8EERavi 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
5EEAvrim Blum, R. Ravi, Santosh Vempala: A Constant-factor Approximation Algorithm for the k MST Problem (Extended Abstract). STOC 1996: 442-448
1995
4EEBaruch Awerbuch, Yossi Azar, Avrim Blum, Santosh Vempala: Improved approximation guarantees for minimum-weight k-trees and prize-collecting salesmen. STOC 1995: 277-283
3EEAvrim Blum, Prasad Chalasani, Santosh Vempala: A constant-factor approximation for the k-MST problem in the plane. STOC 1995: 294-302
1994
2EEVivek 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

Coauthor Index

1Sanjeev Arora [81]
2Vivek Arora [2]
3Rosa I. Arriaga [25] [71]
4Baruch Awerbuch [4] [14]
5Yossi Azar [4] [14]
6Maria-Florina Balcan (Maria-Florina Popa) [61] [70] [98]
7Imre Bárány [65] [86]
8Alexandre Belloni [89]
9Dimitris Bertsimas [42] [55] [93]
10Margrét V. Bjarnadóttir [93]
11Avrim Blum [3] [4] [5] [6] [13] [14] [15] [16] [21] [26] [61] [70] [98]
12Claudson F. Bornstein [43] [49]
13S. Charles Brubaker [96] [100] [104] [108]
14Robert D. Carr [28] [30] [39] [50]
15Prasad Chalasani [3] [13]
16Karthekeyan Chandrasekaran [103] [105] [107]
17David Cheng [64] [79]
18Joseph Cheriyan [38] [41] [45] [75]
19Daniel Dadush [105]
20Amit Deshpande [67] [74] [82] [85] [103] [107]
21Petros Drineas [23] [51]
22John Dunagan [35] [36] [53] [58] [94]
23Megan Elmore [99]
24Nick Feamster [91] [99]
25Robert M. Freund [89]
26Alan M. Frieze [6] [15] [19] [23] [51] [54] [97]
27Naveen Garg [1]
28Navin Goyal [95] [106]
29Piotr Indyk [9]
30Adam Tauman Kalai (Adam Kalai) [31] [40] [48] [62] [69]
31Michael A. Kane [93]
32Ravi Kannan (Ravindran Kannan) [6] [8] [10] [15] [19] [20] [23] [32] [51] [54] [56] [57] [63] [64] [66] [79] [92] [102]
33Marek Karpinski [63]
34Goran Konjevod [16] [26]
35Andrew Kotlov [7]
36J. Christian Kryder [93]
37László Lovász [7] [46] [47] [59] [68] [72] [81] [84] [87]
38Jacques Mandler [30]
39Joseph S. B. Mitchell [13]
40Murtaza Motiwala [99]
41Rajeev Motwani [9]
42Alantha Newman [37]
43Ilan Newman [81]
44Rudra Pandey [93]
45Christos H. Papadimitriou [17] [27] [29] [76]
46David Pritchard [80]
47Yuval Rabani [81]
48Yuri Rabinovich [81]
49Luis Rademacher [60] [67] [73] [78] [82] [83] [95] [106]
50Prabhakar Raghavan [9] [17] [27]
51Anirudh Ramachandran [91]
52R. Ravi [5] [16] [21] [26]
53Hadi Salmasian [57] [66] [92]
54Huzur Saran [2]
55Aman Singla [1]
56Daniel Stefankovic [77] [88] [101]
57Hisao Tamaki [17] [27]
58Prasad Tetali [10] [11] [20] [34]
59Vijay V. Vazirani [2]
60Wenceslas Fernandez de la Vega [63]
61Juan Vera [97]
62Adrian Vetta [32] [33] [41] [45] [56] [65] [75] [86]
63Eric Vigoda [77] [88] [101]
64V. Vinay [23] [51]
65Berthold Vöcking [24]
66Grant Wang [44] [52] [64] [67] [79] [82] [93]
67Mihalis Yannakakis [22]

Colors in the list of coauthors

Copyright © Tue Nov 3 08:52:44 2009 by Michael Ley (ley@uni-trier.de)