2013
146The Complexity of Approximating Vertex Expansion. Anand Louis, Prasad Raghavendra, Santosh Vempala. CoRR (abs/1304.3139) (2013). Web SearchBibTeXDownload
145Nimble Algorithms for Cloud Computing. Ravindran Kannan, Santosh Vempala. CoRR (abs/1304.3162) (2013). Web SearchBibTeXDownload
144The approximate rank of a matrix and its algorithmic applications: approximate rank. Noga Alon, Troy Lee, Adi Shraibman, Santosh Vempala. STOC 2013, 675-684. Web SearchBibTeXDownload
143Statistical algorithms and a lower bound for detecting planted cliques. Vitaly Feldman, Elena Grigorescu, Lev Reyzin, Santosh Vempala, Ying Xiao. STOC 2013, 655-664. Web SearchBibTeXDownload
2012
142Modeling high-dimensional data: technical perspective. Santosh Vempala. Commun. ACM (55): 112 (2012). Web SearchBibTeXDownload
141The Complexity of Statistical Algorithms. Vitaly Feldman, Elena Grigorescu, Lev Reyzin, Santosh Vempala. CoRR (abs/1201.1214) (2012). Web SearchBibTeXDownload
140The Cutting Plane Method is Polynomial for Perfect Matchings. Karthekeyan Chandrasekaran, László A. Végh, Santosh Vempala. CoRR (abs/1207.5813) (2012). Web SearchBibTeXDownload
139Deterministic 2^{O(n)} Algorithms for M-Ellipsoids, Lattice Problems and Volume Estimation. Daniel Dadush, Santosh Vempala. CoRR (abs/1201.5972) (2012). Web SearchBibTeXDownload
138Statistical Algorithms and a Lower Bound for Planted Clique. Vitaly Feldman, Elena Grigorescu, Lev Reyzin, Santosh Vempala, Ying Xiao. Electronic Colloquium on Computational Complexity (ECCC) (19): 64 (2012). Web SearchBibTeXDownload
137The Approximate Rank of a Matrix and its Algorithmic Applications. Noga Alon, Santosh Vempala. Electronic Colloquium on Computational Complexity (ECCC) (19): 169 (2012). Web SearchBibTeXDownload
136The Cutting Plane Method Is Polynomial for Perfect Matchings. Karthekeyan Chandrasekaran, László A. Végh, Santosh Vempala. FOCS 2012, 571-580. Web SearchBibTeXDownload
135Randomly-oriented k-d Trees Adapt to Intrinsic Dimension. Santosh Vempala. FSTTCS 2012, 48-57. Web SearchBibTeXDownload
134A Deterministic Polynomial-Time Approximation Scheme for Counting Knapsack Solutions. Daniel Stefankovic, Santosh Vempala, Eric Vigoda. SIAM J. Comput. (41): 356-366 (2012). Web SearchBibTeXDownload
133Local Versus Global Properties of Metric Spaces. Sanjeev Arora, László Lovász, Ilan Newman, Yuval Rabani, Yuri Rabinovich, Santosh Vempala. SIAM J. Comput. (41): 250-271 (2012). Web SearchBibTeXDownload
132Effective Principal Component Analysis. Santosh Vempala. SISAP 2012, 1-7. Web SearchBibTeXDownload
131Deterministic construction of an approximate M-ellipsoid and its applications to derandomizing lattice algorithms. Daniel Dadush, Santosh Vempala. SODA 2012, 1445-1456. Web SearchBibTeXDownload
130Many sparse cuts via higher eigenvalues. Anand Louis, Prasad Raghavendra, Prasad Tetali, Santosh Vempala. STOC 2012, 1131-1140. Web SearchBibTeXDownload
2011
129On Noise-Tolerant Learning of Sparse Parities and Related Problems. Elena Grigorescu, Lev Reyzin, Santosh Vempala. ALT 2011, 413-424. Web SearchBibTeXDownload
128Semantic Communication for Simple Goals Is Equivalent to On-line Learning. Brendan Juba, Santosh Vempala. ALT 2011, 277-291. Web SearchBibTeXDownload
127Algorithmic Extensions of Cheeger's Inequality to Higher Eigenvalues and Partitions. Anand Louis, Prasad Raghavendra, Prasad Tetali, Santosh Vempala. APPROX-RANDOM 2011, 315-326. Web SearchBibTeXDownload
126Structure from Local Optima: Learning Subspace Juntas via Higher Order PCA. Santosh Vempala, Ying Xiao. CoRR (abs/1108.3329) (2011). Web SearchBibTeXDownload
125Many Sparse Cuts via Higher Eigenvalues. Anand Louis, Prasad Raghavendra, Prasad Tetali, Santosh Vempala. CoRR (abs/1111.0965) (2011). Web SearchBibTeXDownload
124A Discrepancy based Approach to Integer Programming. Karthekeyan Chandrasekaran, Santosh Vempala. CoRR (abs/1111.4649) (2011). Web SearchBibTeXDownload
123Deterministic Construction of an Approximate M-Ellipsoid and its Application to Derandomizing Lattice Algorithms. Daniel Dadush, Santosh Vempala. CoRR (abs/1107.5478) (2011). Web SearchBibTeXDownload
122Algorithms for Implicit Hitting Set Problems. Karthekeyan Chandrasekaran, Richard Karp, Erick Moreno-Centeno, Santosh Vempala. CoRR (abs/1102.1472) (2011). Web SearchBibTeXDownload
121Enumerative Lattice Algorithms in any Norm Via M-ellipsoid Coverings. Daniel Dadush, Chris Peikert, Santosh Vempala. FOCS 2011, 580-589. Web SearchBibTeXDownload
120An FPTAS for #Knapsack and Related Counting Problems. Parikshit Gopalan, Adam Klivans, Raghu Meka, Daniel Stefankovic, Santosh Vempala, Eric Vigoda. FOCS 2011, 817-826. Web SearchBibTeXDownload
119LifeNet: a flexible ad hoc networking solution for transient environments. Hrushikesh Mehendale, Ashwin Paranjpe, Santosh Vempala. SIGCOMM 2011, 446-447. Web SearchBibTeXDownload
2010
118A Deterministic Polynomial-time Approximation Scheme for Counting Knapsack Solutions. Daniel Stefankovic, Santosh Vempala, Eric Vigoda. CoRR (abs/1008.1687) (2010). Web SearchBibTeXDownload
117Enumerative Algorithms for the Shortest and Closest Lattice Vector Problems in Any Norm via M-Ellipsoid Coverings. Daniel Dadush, Chris Peikert, Santosh Vempala. CoRR (abs/1011.5666) (2010). Web SearchBibTeXDownload
116Logconcave Random Graphs. Alan M. Frieze, Santosh Vempala, Juan Vera. Electr. J. Comb. (17) (2010). Web SearchBibTeXDownload
115Corrigendum: A Random Sampling Algorithm for Learning an Intersection of Halfspaces. Santosh Vempala. FOCS 2010, 123. Web SearchBibTeXDownload
114Learning Convex Concepts from Gaussian Distributions with PCA. Santosh Vempala. FOCS 2010, 124-130. Web SearchBibTeXDownload
113Recent Progress and Open Problems in Algorithmic Convex Geometry. Santosh Vempala. FSTTCS 2010, 42-64. Web SearchBibTeXDownload
112A New Approach to Strongly Polynomial Linear Programming. Mihály Bárász, Santosh Vempala. ICS 2010, 42-48. Web SearchBibTeXDownload
111A random-sampling-based algorithm for learning intersections of halfspaces. Santosh Vempala. J. ACM (57): 32 (2010). Web SearchBibTeXDownload
110On Nash-Equilibria of Approximation-Stable Games. Pranjal Awasthi, Maria-Florina Balcan, Avrim Blum, Or Sheffet, Santosh Vempala. SAGT 2010, 78-89. Web SearchBibTeXDownload
109Circumventing censorship with collage. Sam Burnett, Nick Feamster, Santosh Vempala. SIGCOMM 2010, 471-472. Web SearchBibTeXDownload
108Thin Partitions: Isoperimetric Inequalities and a Sampling Algorithm for Star Shaped Bodies. Karthekeyan Chandrasekaran, Daniel Dadush, Santosh Vempala. SODA 2010, 1630-1645. Web SearchBibTeXDownload
107Chipping Away at Censorship Firewalls with User-Generated Content. Sam Burnett, Nick Feamster, Santosh Vempala. USENIX Security Symposium 2010, 463-468. Web SearchBibTeXDownload
2009
106Random Tensors and Planted Cliques. S. Charles Brubaker, Santosh Vempala. APPROX-RANDOM 2009, 406-419. Web SearchBibTeXDownload
105Sampling s-Concave Functions: The Limit of Convexity Based Isoperimetry. Karthekeyan Chandrasekaran, Amit Deshpande, Santosh Vempala. APPROX-RANDOM 2009, 420-433. Web SearchBibTeXDownload
104Thin Partitions: Isoperimetric Inequalities and Sampling Algorithms for some Nonconvex Families. Karthekeyan Chandrasekaran, Daniel Dadush, Santosh Vempala. CoRR (abs/0904.0583) (2009). Web SearchBibTeXDownload
103The Limit of Convexity Based Isoperimetry: Sampling Harmonic-Concave Functions. Karthekeyan Chandrasekaran, Amit Deshpande, Santosh Vempala. CoRR (abs/0906.2448) (2009). Web SearchBibTeXDownload
102Spectral Algorithms. Ravi Kannan, Santosh Vempala. Foundations and Trends in Theoretical Computer Science (4): 157-288 (2009). Web SearchBibTeXDownload
101Design of a blood flow system. Adebola Osuntogun, Stephen Thomas, John Pitman, Sridhar Basavaraju, Bright Mulenga, Santosh Vempala. ICTD 2009, 481. Web SearchBibTeXDownload
100Design and deployment of a blood safety monitoring tool. Stephen Thomas, Adebola Osuntogun, John Pitman, Bright Mulenga, Santosh Vempala. ICTD 2009, 280-287. Web SearchBibTeXDownload
99Adaptive simulated annealing: A near-optimal connection between sampling and counting. Daniel Stefankovic, Santosh Vempala, Eric Vigoda. J. ACM (56) (2009). Web SearchBibTeXDownload
98An Efficient Rescaled Perceptron Algorithm for Conic Systems. Alexandre Belloni, Robert M. Freund, Santosh Vempala. Math. Oper. Res. (34): 621-641 (2009). Web SearchBibTeXDownload
97Expanders via random spanning trees. Navin Goyal, Luis Rademacher, Santosh Vempala. SODA 2009, 576-585. Web SearchBibTeXDownload
2008
96Expanders via Random Spanning Trees. Navin Goyal, Luis Rademacher, Santosh Vempala. CoRR (abs/0807.1496) (2008). Web SearchBibTeXDownload
95Isotropic PCA and Affine-Invariant Clustering. S. Charles Brubaker, Santosh Vempala. FOCS (abs/0804.3575): 551-560 (2008). Web SearchBibTeXDownload
94A simple polynomial-time rescaling algorithm for solving linear programs. John Dunagan, Santosh Vempala. Math. Program. (114): 101-114 (2008). Web SearchBibTeXDownload
93Algorithmic Prediction of Health-Care Costs. Dimitris Bertsimas, Margrét V. Bjarnadóttir, Michael A. Kane, J. Christian Kryder, Rudra Pandey, Santosh Vempala, Grant Wang. Operations Research (56): 1382-1392 (2008). Web SearchBibTeXDownload
92The Spectral Method for General Mixture Models. Ravindran Kannan, Hadi Salmasian, Santosh Vempala. SIAM J. Comput. (38): 1141-1156 (2008). Web SearchBibTeXDownload
91Path splicing. Murtaza Motiwala, Megan Elmore, Nick Feamster, Santosh Vempala. SIGCOMM 2008, 27-38. Web SearchBibTeXDownload
90Logconcave random graphs. Alan M. Frieze, Santosh Vempala, Juan Vera. STOC 2008, 779-788. Web SearchBibTeXDownload
89A discriminative framework for clustering via similarity functions. Maria-Florina Balcan, Avrim Blum, Santosh Vempala. STOC 2008, 671-680. Web SearchBibTeXDownload
2007
88Filtering spam with behavioral blacklisting. Anirudh Ramachandran, Nick Feamster, Santosh Vempala. ACM Conference on Computer and Communications Security 2007, 342-351. Web SearchBibTeXDownload
87Spectral Algorithms for Learning and Clustering. Santosh Vempala. COLT 2007, 3-4. Web SearchBibTeXDownload
86An Efficient Re-scaled Perceptron Algorithm for Conic Systems. Alexandre Belloni, Robert M. Freund, Santosh Vempala. COLT 2007, 393-408. Web SearchBibTeXDownload
85Adaptive Simulated Annealing: A Near-optimal Connection between Sampling and Counting. Daniel Stefankovic, Santosh Vempala, Eric Vigoda. FOCS 2007, 183-193. Web SearchBibTeXDownload
84The geometry of logconcave functions and sampling algorithms. László Lovász, Santosh Vempala. Random Struct. Algorithms (30): 307-358 (2007). Web SearchBibTeXDownload
83Nash equilibria in random games. Imre Bárány, Santosh Vempala, Adrian Vetta. Random Struct. Algorithms (31): 391-405 (2007). Web SearchBibTeXDownload
2006
82A divide-and-merge methodology for clustering. David Cheng, Ravi Kannan, Ravi Kannan, Grant Wang. ACM Trans. Database Syst. (31): 1499-1525 (2006). Web SearchBibTeXDownload
81Adaptive Sampling and Fast Low-Rank Matrix Approximation. Amit Deshpande, Santosh Vempala. APPROX-RANDOM 2006, 292-303. Web SearchBibTeXDownload
80Network Design Via Iterative Rounding Of Setpair Relaxations. Joseph Cheriyan, Santosh Vempala, Adrian Vetta. Combinatorica (26): 255-275 (2006). Web SearchBibTeXDownload
79On The Approximability Of The Traveling Salesman Problem. Christos H. Papadimitriou, Santosh Vempala. Combinatorica (26): 101-120 (2006). Web SearchBibTeXDownload
78Adaptive Simulated Annealing: A Near-optimal Connection between Sampling and Counting. Daniel Stefankovic, Santosh Vempala, Eric Vigoda. CoRR (abs/cs/0612058) (2006). Web SearchBibTeXDownload
77Dispersion of Mass and the Complexity of Randomized Geometric Algorithms. Luis Rademacher, Santosh Vempala. FOCS 2006, 729-738. Web SearchBibTeXDownload
76Fast Algorithms for Logconcave Functions: Sampling, Rounding, Integration and Optimization. László Lovász, Santosh Vempala. FOCS 2006, 57-68. Web SearchBibTeXDownload
75Simulated annealing in convex bodies and an O*(n4) volume algorithm. László Lovász, Santosh Vempala. J. Comput. Syst. Sci. (72): 392-417 (2006). Web SearchBibTeXDownload
74Kernels as features: On kernels, margins, and low-dimensional mappings. Maria-Florina Balcan, Avrim Blum, Santosh Vempala. Machine Learning (65): 79-94 (2006). Web SearchBibTeXDownload
73An algorithmic theory of learning: Robust concepts and random projection. Rosa I. Arriaga, Santosh Vempala. Machine Learning (63): 161-182 (2006). Web SearchBibTeXDownload
72Simulated Annealing for Convex Optimization. Adam Tauman Kalai, Santosh Vempala. Math. Oper. Res. (31): 253-266 (2006). Web SearchBibTeXDownload
71Hit-and-Run from a Corner. László Lovász, Santosh Vempala. SIAM J. Comput. (35): 985-1005 (2006). Web SearchBibTeXDownload
70Local versus global properties of metric spaces. Sanjeev Arora, László Lovász, Ilan Newman, Yuval Rabani, Yuri Rabinovich, Santosh Vempala. SODA 2006, 41-50. Web SearchBibTeXDownload
69Matrix approximation and projective clustering via volume sampling. Amit Deshpande, Luis Rademacher, Santosh Vempala, Grant Wang. SODA 2006, 1117-1126. Web SearchBibTeXDownload
68Symmetric network computation. David Pritchard, Santosh Vempala. SPAA 2006, 261-270. Web SearchBibTeXDownload
67Matrix Approximation and Projective Clustering via Volume Sampling. Amit Deshpande, Luis Rademacher, Santosh Vempala, Grant Wang. Theory of Computing (2): 225-247 (2006). Web SearchBibTeXDownload
2005
66The Spectral Method for General Mixture Models. Ravindran Kannan, Hadi Salmasian, Santosh Vempala. COLT 2005, 444-457. Web SearchBibTeXDownload
65Nash Equilibria in Random Games. Imre Bárány, Santosh Vempala, Adrian Vetta. FOCS 2005, 123-131. Web SearchBibTeXDownload
64Efficient algorithms for online decision problems. Adam Tauman Kalai, Santosh Vempala. J. Comput. Syst. Sci. (71): 291-307 (2005). Web SearchBibTeXDownload
63A divide-and-merge methodology for clustering. David Cheng, Ravi Kannan, Ravi Kannan, Grant Wang. PODS 2005, 196-205. Web SearchBibTeXDownload
62Tensor decomposition and approximation schemes for constraint satisfaction problems. Wenceslas Fernandez de la Vega, Marek Karpinski, Ravi Kannan, Santosh Vempala. STOC 2005, 747-754. Web SearchBibTeXDownload
2004
61On Kernels, Margins, and Low-Dimensional Mappings. Maria-Florina Balcan, Avrim Blum, Santosh Vempala. ALT 2004, 194-205. Web SearchBibTeXDownload
60The Spectral Method for Mixture Models. Hadi Salmasian, Ravindran Kannan, Santosh Vempala. Electronic Colloquium on Computational Complexity (ECCC) 2004. Web SearchBibTeXDownload
59Testing Geometric Convexity. Luis Rademacher, Santosh Vempala. FSTTCS 2004, 469-480. Web SearchBibTeXDownload
58Fast monte-carlo algorithms for finding low-rank approximations. Alan M. Frieze, Ravi Kannan, Santosh Vempala. J. ACM (51): 1025-1041 (2004). Web SearchBibTeXDownload
57Solving convex programs by random walks. Dimitris Bertsimas, Santosh Vempala. J. ACM (51): 540-556 (2004). Web SearchBibTeXDownload
56On clusterings: Good, bad and spectral. Ravi Kannan, Santosh Vempala, Adrian Vetta. J. ACM (51): 497-515 (2004). Web SearchBibTeXDownload
55Optimal outlier removal in high-dimensional spaces. John Dunagan, Santosh Vempala. J. Comput. Syst. Sci. (68): 335-373 (2004). Web SearchBibTeXDownload
54A spectral algorithm for learning mixture models. Santosh Vempala, Grant Wang. J. Comput. Syst. Sci. (68): 841-860 (2004). Web SearchBibTeXDownload
53Clustering Large Graphs via the Singular Value Decomposition. Petros Drineas, Alan M. Frieze, Ravi Kannan, Santosh Vempala, V. Vinay. Machine Learning (56): 9-33 (2004). Web SearchBibTeXDownload
52On the Held-Karp relaxation for the asymmetric and symmetric traveling salesman problems. Robert D. Carr, Santosh Vempala. Math. Program. (100): 569-587 (2004). Web SearchBibTeXDownload
51A simple polynomial-time rescaling algorithm for solving linear programs. John Dunagan, Santosh Vempala. STOC 2004, 315-320. Web SearchBibTeXDownload
50Hit-and-run from a corner. László Lovász, Santosh Vempala. STOC 2004, 310-314. Web SearchBibTeXDownload
49Flow metrics. Claudson F. Bornstein, Santosh Vempala. Theor. Comput. Sci. (321): 13-24 (2004). Web SearchBibTeXDownload
2003
48Efficient Algorithms for Online Decision Problems. Adam Kalai, Santosh Vempala. COLT 2003, 26-40. Web SearchBibTeXDownload
47Simulated Annealing in Convex Bodies and an 0*(n4) Volume Algorithm. László Lovász, Santosh Vempala. FOCS 2003, 650-659. Web SearchBibTeXDownload
46Logconcave Functions: Geometry and Efficient Sampling Algorithms. László Lovász, Santosh Vempala. FOCS 2003, 640-649. Web SearchBibTeXDownload
45An Approximation Algorithm for the Minimum-Cost k-Vertex Connected Subgraph. Joseph Cheriyan, Santosh Vempala, Adrian Vetta. SIAM J. Comput. (32): 1050-1055 (2003). Web SearchBibTeXDownload
2002
44A Spectral Algorithm for Learning Mixtures of Distributions. Santosh Vempala, Grant Wang. FOCS 2002, 113. Web SearchBibTeXDownload
43Efficient Algorithms for Universal Portfolios. Adam Kalai, Santosh Vempala. Journal of Machine Learning Research (3): 423-440 (2002). Web SearchBibTeXDownload
42Flow Metrics. Claudson F. Bornstein, Santosh Vempala. LATIN 2002, 516-527. Web SearchBibTeXDownload
41Randomized metarounding. Robert D. Carr, Santosh Vempala. Random Struct. Algorithms (20): 343-352 (2002). Web SearchBibTeXDownload
40Solving convex programs by random walks. Dimitris Bertsimas, Santosh Vempala. STOC 2002, 109-115. Web SearchBibTeXDownload
39Approximation algorithms for minimum-cost k-vertex connected subgraphs. Joseph Cheriyan, Santosh Vempala, Adrian Vetta. STOC 2002, 306-312. Web SearchBibTeXDownload
2001
38Random Sampling of Euler Tours. Prasad Tetali, Santosh Vempala. Algorithmica (30): 376-385 (2001). Web SearchBibTeXDownload
37Edge Covers of Setpairs and the Iterative Rounding Method. Joseph Cheriyan, Santosh Vempala. IPCO 2001, 30-44. Web SearchBibTeXDownload
36Fences Are Futile: On Relaxations for the Linear Ordering Problem. Alantha Newman, Santosh Vempala. IPCO 2001, 333-347. Web SearchBibTeXDownload
35On Euclidean Embeddings and Bandwidth Minimization. John Dunagan, Santosh Vempala. RANDOM-APPROX 2001, 229-240. Web SearchBibTeXDownload
34Optimal outlier removal in high-dimensional. John Dunagan, Santosh Vempala. STOC 2001, 627-636. Web SearchBibTeXDownload
2000
33Factor 4/3 approximations for minimum 2-connected subgraphs. Santosh Vempala, Adrian Vetta. APPROX 2000, 262-273. Web SearchBibTeXDownload
32Efficient Algorithms for Universal Portfolios. Adam Kalai, Santosh Vempala. FOCS 2000, 486-491. Web SearchBibTeXDownload
31On Clusterings - Good, Bad and Spectral. Ravi Kannan, Santosh Vempala, Adrian Vetta. FOCS 2000, 367-377. Web SearchBibTeXDownload
30Latent Semantic Indexing: A Probabilistic Analysis. Christos H. Papadimitriou, Prabhakar Raghavan, Hisao Tamaki, Santosh Vempala. J. Comput. Syst. Sci. (61): 217-235 (2000). Cited by 463Web SearchBibTeXDownload
29Towards a 4/3 approximation for the asymmetric traveling salesman problem. Robert D. Carr, Santosh Vempala, Jacques Mandler. SODA 2000, 116-125. Web SearchBibTeXDownload
28On the approximability of the traveling salesman problem (extended abstract). Christos H. Papadimitriou, Santosh Vempala. STOC 2000, 126-133. Web SearchBibTeXDownload
27Randomized metarounding (extended abstract). Robert D. Carr, Santosh Vempala. STOC 2000, 58-62. Web SearchBibTeXDownload
26Semi-definite relaxations for minimum bandwidth and other vertex-ordering problems. Avrim Blum, Goran Konjevod, R. Ravi, Santosh Vempala. Theor. Comput. Sci. (235): 25-42 (2000). Web SearchBibTeXDownload
1999
25An Algorithmic Theory of Learning: Robust Concepts and Random Projection. Rosa I. Arriaga, Santosh Vempala. FOCS 1999, 616-623. Web SearchBibTeXDownload
24Approximating Multicast Congestion. Santosh Vempala, Berthold Vöcking. ISAAC 1999, 367-372. Web SearchBibTeXDownload
23A Constant-Factor Approximation Algorithm for the k-MST Problem. Avrim Blum, R. Ravi, Santosh Vempala. J. Comput. Syst. Sci. (58): 101-108 (1999). Web SearchBibTeXDownload
22Simple Markov-chain algorithms for generating bipartite graphs and tournaments. Ravi Kannan, Prasad Tetali, Santosh Vempala. Random Struct. Algorithms (14): 293-308 (1999). Web SearchBibTeXDownload
21A Convex Relaxation for the Asymmetric TSP. Santosh Vempala, Mihalis Yannakakis. SODA 1999, 975-976. Web SearchBibTeXDownload
20Clustering in Large Graphs and Matrices. Petros Drineas, Alan M. Frieze, Ravi Kannan, Santosh Vempala, V. Vinay. SODA 1999, 291-299. Web SearchBibTeXDownload
1998
19A Polynomial-Time Algorithm for Learning Noisy Linear Threshold Functions. Avrim Blum, Alan M. Frieze, Ravi Kannan, Santosh Vempala. Algorithmica (22): 35-52 (1998). Web SearchBibTeXDownload
18Random Projection: A New Approach to VLSI Layout. Santosh Vempala. FOCS 1998, 389-395. Web SearchBibTeXDownload
17Fast Monte-Carlo Algorithms for Finding Low-Rank Approximations. Alan M. Frieze, Ravi Kannan, Santosh Vempala. FOCS 1998, 370-378. Web SearchBibTeXDownload
16Latent Semantic Indexing: A Probabilistic Analysis. Christos H. Papadimitriou, Prabhakar Raghavan, Hisao Tamaki, Santosh Vempala. PODS 1998, 159-168. Cited by 463Web SearchBibTeXDownload
15New Approximation Guarantees for Minimum-Weight k-Trees and Prize-Collecting Salesmen. Baruch Awerbuch, Yossi Azar, Avrim Blum, Santosh Vempala. SIAM J. Comput. (28): 254-262 (1998). Web SearchBibTeXDownload
14A Constant-Factor Approximation Algorithm for the Geometric k-MST Problem in the Plane. Joseph S. B. Mitchell, Avrim Blum, Prasad Chalasani, Santosh Vempala. SIAM J. Comput. (28): 771-781 (1998). Web SearchBibTeXDownload
13Semi-Definite Relaxations for Minimum Bandwidth and other Vertex-Ordering Problems. Avrim Blum, Goran Konjevod, R. Ravi, Santosh Vempala. STOC 1998, 100-105. Web SearchBibTeXDownload
1997
12The Colin de Verdière Number and Sphere Representations of a Graph. Andrew Kotlov, László Lovász, Santosh Vempala. Combinatorica (17): 483-521 (1997). Web SearchBibTeXDownload
11A Random Sampling Based Algorithm for Learning the Intersection of Half-spaces. Santosh Vempala. FOCS 1997, 508-513. Web SearchBibTeXDownload
10Random Sampling of Euler Tours. Prasad Tetali, Santosh Vempala. RANDOM 1997, 57-66. Web SearchBibTeXDownload
9Simple Markov-Chain Algorithms for Generating Bipartite Graphs and Tournaments (Extended Abstract). Ravi Kannan, Prasad Tetali, Santosh Vempala. SODA 1997, 193-200. Web SearchBibTeXDownload
8Sampling Lattice Points. Ravi Kannan, Santosh Vempala. STOC 1997, 696-700. Web SearchBibTeXDownload
7Locality-Preserving Hashing in Multidimensional Spaces. Piotr Indyk, Rajeev Motwani, Prabhakar Raghavan, Santosh Vempala. STOC 1997, 618-625. Cited by 98Web SearchBibTeXDownload
1996
6A Polynomial-Time Algorithm for Learning Noisy Linear Threshold Functions. Avrim Blum, Alan M. Frieze, Ravi Kannan, Santosh Vempala. FOCS 1996, 330-338. Web SearchBibTeXDownload
5A Constant-factor Approximation Algorithm for the k MST Problem (Extended Abstract). Avrim Blum, R. Ravi, Santosh Vempala. STOC 1996, 442-448. Web SearchBibTeXDownload
1995
4Improved approximation guarantees for minimum-weight k-trees and prize-collecting salesmen. Baruch Awerbuch, Yossi Azar, Avrim Blum, Santosh Vempala. STOC 1995, 277-283. Web SearchBibTeXDownload
3A constant-factor approximation for the k-MST problem in the plane. Avrim Blum, Prasad Chalasani, Santosh Vempala. STOC 1995, 294-302. Web SearchBibTeXDownload
1994
2A Limited-Backtrack Greedy Schema for Approximation Algorithms. Vivek Arora, Santosh Vempala, Huzur Saran, Vijay V. Vazirani. FSTTCS 1994, 318-329. Web SearchBibTeXDownload
1993
1Improved Approximation Algorithms for Biconnected Subgraphs via Better Lower Bounding Techniques. Naveen Garg, Santosh Vempala, Aman Singla. SODA 1993, 103-111. Web SearchBibTeXDownload
from DBLP and Google Scholar
Developed by the Database Group at the University of Wisconsin and Yahoo! Research