Please note: This is a beta version of the new dblp website.
You can find the classic dblp view of this page here.
You can find the classic dblp view of this page here.
Santosh Vempala
2010 – today
- 2013
[c85]Vitaly Feldman, Elena Grigorescu, Lev Reyzin, Santosh Vempala, Ying Xiao: Statistical algorithms and a lower bound for detecting planted cliques. STOC 2013: 655-664- [c84]Noga Alon, Troy Lee, Adi Shraibman, Santosh Vempala: The approximate rank of a matrix and its algorithmic applications: approximate rank. STOC 2013: 675-684
- [i24]Anand Louis, Prasad Raghavendra, Santosh Vempala: The Complexity of Approximating Vertex Expansion. CoRR abs/1304.3139 (2013)
- [i23]
- 2012
- [j43]Santosh Vempala: Modeling high-dimensional data: technical perspective. Commun. ACM 55(2): 112 (2012)
- [j42]Sanjeev Arora, László Lovász, Ilan Newman, Yuval Rabani, Yuri Rabinovich, Santosh Vempala: Local Versus Global Properties of Metric Spaces. SIAM J. Comput. 41(1): 250-271 (2012)
- [j41]Daniel Stefankovic, Santosh Vempala, Eric Vigoda: A Deterministic Polynomial-Time Approximation Scheme for Counting Knapsack Solutions. SIAM J. Comput. 41(2): 356-366 (2012)
- [c83]Karthekeyan Chandrasekaran, László A. Végh, Santosh Vempala: The Cutting Plane Method Is Polynomial for Perfect Matchings. FOCS 2012: 571-580
- [c82]
- [c81]
- [c80]Daniel Dadush, Santosh Vempala: Deterministic construction of an approximate M-ellipsoid and its applications to derandomizing lattice algorithms. SODA 2012: 1445-1456
- [c79]Anand Louis, Prasad Raghavendra, Prasad Tetali, Santosh Vempala: Many sparse cuts via higher eigenvalues. STOC 2012: 1131-1140
- [i22]Vitaly Feldman, Elena Grigorescu, Lev Reyzin, Santosh Vempala: The Complexity of Statistical Algorithms. CoRR abs/1201.1214 (2012)
- [i21]Daniel Dadush, Santosh Vempala: Deterministic 2^{O(n)} Algorithms for M-Ellipsoids, Lattice Problems and Volume Estimation. CoRR abs/1201.5972 (2012)
- [i20]Karthekeyan Chandrasekaran, László A. Végh, Santosh Vempala: The Cutting Plane Method is Polynomial for Perfect Matchings. CoRR abs/1207.5813 (2012)
- [i19]Vitaly Feldman, Elena Grigorescu, Lev Reyzin, Santosh Vempala, Ying Xiao: Statistical Algorithms and a Lower Bound for Planted Clique. Electronic Colloquium on Computational Complexity (ECCC) 19: 64 (2012)
- [i18]Noga Alon, Santosh Vempala: The Approximate Rank of a Matrix and its Algorithmic Applications. Electronic Colloquium on Computational Complexity (ECCC) 19: 169 (2012)
- 2011
- [c78]Brendan Juba, Santosh Vempala: Semantic Communication for Simple Goals Is Equivalent to On-line Learning. ALT 2011: 277-291
- [c77]Elena Grigorescu, Lev Reyzin, Santosh Vempala: On Noise-Tolerant Learning of Sparse Parities and Related Problems. ALT 2011: 413-424
- [c76]Anand Louis, Prasad Raghavendra, Prasad Tetali, Santosh Vempala: Algorithmic Extensions of Cheeger's Inequality to Higher Eigenvalues and Partitions. APPROX-RANDOM 2011: 315-326
- [c75]Daniel Dadush, Chris Peikert, Santosh Vempala: Enumerative Lattice Algorithms in any Norm Via M-ellipsoid Coverings. FOCS 2011: 580-589
- [c74]Parikshit Gopalan, Adam Klivans, Raghu Meka, Daniel Stefankovic, Santosh Vempala, Eric Vigoda: An FPTAS for #Knapsack and Related Counting Problems. FOCS 2011: 817-826
- [c73]Hrushikesh Mehendale, Ashwin Paranjpe, Santosh Vempala: LifeNet: a flexible ad hoc networking solution for transient environments. SIGCOMM 2011: 446-447
- [c72]Karthekeyan Chandrasekaran, Richard M. Karp, Erick Moreno-Centeno, Santosh Vempala: Algorithms for Implicit Hitting Set Problems. SODA 2011: 614-629
- [i17]Karthekeyan Chandrasekaran, Richard M. Karp, Erick Moreno-Centeno, Santosh Vempala: Algorithms for Implicit Hitting Set Problems. CoRR abs/1102.1472 (2011)
- [i16]Daniel Dadush, Santosh Vempala: Deterministic Construction of an Approximate M-Ellipsoid and its Application to Derandomizing Lattice Algorithms. CoRR abs/1107.5478 (2011)
- [i15]Santosh Vempala, Ying Xiao: Structure from Local Optima: Learning Subspace Juntas via Higher Order PCA. CoRR abs/1108.3329 (2011)
- [i14]Anand Louis, Prasad Raghavendra, Prasad Tetali, Santosh Vempala: Many Sparse Cuts via Higher Eigenvalues. CoRR abs/1111.0965 (2011)
- [i13]Karthekeyan Chandrasekaran, Santosh Vempala: A Discrepancy based Approach to Integer Programming. CoRR abs/1111.4649 (2011)
- 2010
- [j40]
- [j39]Santosh Vempala: A random-sampling-based algorithm for learning intersections of halfspaces. J. ACM 57(6): 32 (2010)
- [c71]Santosh Vempala: Corrigendum: A Random Sampling Algorithm for Learning an Intersection of Halfspaces. FOCS 2010: 123
- [c70]
- [c69]Santosh Vempala: Recent Progress and Open Problems in Algorithmic Convex Geometry. FSTTCS 2010: 42-64
- [c68]Mihály Bárász, Santosh Vempala: A New Approach to Strongly Polynomial Linear Programming. ICS 2010: 42-48
- [c67]Pranjal Awasthi, Maria-Florina Balcan, Avrim Blum, Or Sheffet, Santosh Vempala: On Nash-Equilibria of Approximation-Stable Games. SAGT 2010: 78-89
- [c66]Sam Burnett, Nick Feamster, Santosh Vempala: Circumventing censorship with collage. SIGCOMM 2010: 471-472
- [c65]Karthekeyan Chandrasekaran, Daniel Dadush, Santosh Vempala: Thin Partitions: Isoperimetric Inequalities and a Sampling Algorithm for Star Shaped Bodies. SODA 2010: 1630-1645
- [c64]Sam Burnett, Nick Feamster, Santosh Vempala: Chipping Away at Censorship Firewalls with User-Generated Content. USENIX Security Symposium 2010: 463-468
- [i12]Daniel Stefankovic, Santosh Vempala, Eric Vigoda: A Deterministic Polynomial-time Approximation Scheme for Counting Knapsack Solutions. CoRR abs/1008.1687 (2010)
- [i11]Daniel Dadush, Chris Peikert, Santosh Vempala: Enumerative Algorithms for the Shortest and Closest Lattice Vector Problems in Any Norm via M-Ellipsoid Coverings. CoRR abs/1011.5666 (2010)
2000 – 2009
- 2009
- [j38]Ravi Kannan, Santosh Vempala: Spectral Algorithms. Foundations and Trends in Theoretical Computer Science 4(3-4): 157-288 (2009)
- [j37]Daniel Stefankovic, Santosh Vempala, Eric Vigoda: Adaptive simulated annealing: A near-optimal connection between sampling and counting. J. ACM 56(3) (2009)
- [j36]Alexandre Belloni, Robert M. Freund, Santosh Vempala: An Efficient Rescaled Perceptron Algorithm for Conic Systems. Math. Oper. Res. 34(3): 621-641 (2009)
- [c63]S. Charles Brubaker, Santosh Vempala: Random Tensors and Planted Cliques. APPROX-RANDOM 2009: 406-419
- [c62]Karthekeyan Chandrasekaran, Amit Deshpande, Santosh Vempala: Sampling s-Concave Functions: The Limit of Convexity Based Isoperimetry. APPROX-RANDOM 2009: 420-433
- [c61]Stephen Thomas, Adebola Osuntogun, John Pitman, Bright Mulenga, Santosh Vempala: Design and deployment of a blood safety monitoring tool. ICTD 2009: 280-287
- [c60]Adebola Osuntogun, Stephen Thomas, John Pitman, Sridhar Basavaraju, Bright Mulenga, Santosh Vempala: Design of a blood flow system. ICTD 2009: 481
- [c59]Navin Goyal, Luis Rademacher, Santosh Vempala: Expanders via random spanning trees. SODA 2009: 576-585
- [i10]Karthekeyan Chandrasekaran, Daniel Dadush, Santosh Vempala: Thin Partitions: Isoperimetric Inequalities and Sampling Algorithms for some Nonconvex Families. CoRR abs/0904.0583 (2009)
- [i9]
- [i8]Karthekeyan Chandrasekaran, Amit Deshpande, Santosh Vempala: The Limit of Convexity Based Isoperimetry: Sampling Harmonic-Concave Functions. CoRR abs/0906.2448 (2009)
- 2008
- [j35]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)
- [j34]John Dunagan, Santosh Vempala: A simple polynomial-time rescaling algorithm for solving linear programs. Math. Program. 114(1): 101-114 (2008)
- [j33]Ravindran Kannan, Hadi Salmasian, Santosh Vempala: The Spectral Method for General Mixture Models. SIAM J. Comput. 38(3): 1141-1156 (2008)
- [c58]S. Charles Brubaker, Santosh Vempala: Isotropic PCA and Affine-Invariant Clustering. FOCS 2008: 551-560
- [c57]
- [c56]Maria-Florina Balcan, Avrim Blum, Santosh Vempala: A discriminative framework for clustering via similarity functions. STOC 2008: 671-680
- [c55]
- [i7]S. Charles Brubaker, Santosh Vempala: Isotropic PCA and Affine-Invariant Clustering. CoRR abs/0804.3575 (2008)
- [i6]Navin Goyal, Luis Rademacher, Santosh Vempala: Expanders via Random Spanning Trees. CoRR abs/0807.1496 (2008)
- 2007
- [j32]László Lovász, Santosh Vempala: The geometry of logconcave functions and sampling algorithms. Random Struct. Algorithms 30(3): 307-358 (2007)
- [j31]Imre Bárány, Santosh Vempala, Adrian Vetta: Nash equilibria in random games. Random Struct. Algorithms 31(4): 391-405 (2007)
- [c54]Anirudh Ramachandran, Nick Feamster, Santosh Vempala: Filtering spam with behavioral blacklisting. ACM Conference on Computer and Communications Security 2007: 342-351
- [c53]
- [c52]Alexandre Belloni, Robert M. Freund, Santosh Vempala: An Efficient Re-scaled Perceptron Algorithm for Conic Systems. COLT 2007: 393-408
- [c51]Daniel Stefankovic, Santosh Vempala, Eric Vigoda: Adaptive Simulated Annealing: A Near-optimal Connection between Sampling and Counting. FOCS 2007: 183-193
- 2006
- [j30]Christos H. Papadimitriou, Santosh Vempala: On The Approximability Of The Traveling Salesman Problem. Combinatorica 26(1): 101-120 (2006)
- [j29]Joseph Cheriyan, Santosh Vempala, Adrian Vetta: Network Design Via Iterative Rounding Of Setpair Relaxations. Combinatorica 26(3): 255-275 (2006)
- [j28]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)
- [j27]Rosa I. Arriaga, Santosh Vempala: An algorithmic theory of learning: Robust concepts and random projection. Machine Learning 63(2): 161-182 (2006)
- [j26]Maria-Florina Balcan, Avrim Blum, Santosh Vempala: Kernels as features: On kernels, margins, and low-dimensional mappings. Machine Learning 65(1): 79-94 (2006)
- [j25]Adam Tauman Kalai, Santosh Vempala: Simulated Annealing for Convex Optimization. Math. Oper. Res. 31(2): 253-266 (2006)
- [j24]
- [j23]Amit Deshpande, Luis Rademacher, Santosh Vempala, Grant Wang: Matrix Approximation and Projective Clustering via Volume Sampling. Theory of Computing 2(1): 225-247 (2006)
- [j22]David Cheng, Ravi Kannan, Santosh Vempala, Grant Wang: A divide-and-merge methodology for clustering. ACM Trans. Database Syst. 31(4): 1499-1525 (2006)
- [c50]Amit Deshpande, Santosh Vempala: Adaptive Sampling and Fast Low-Rank Matrix Approximation. APPROX-RANDOM 2006: 292-303
- [c49]László Lovász, Santosh Vempala: Fast Algorithms for Logconcave Functions: Sampling, Rounding, Integration and Optimization. FOCS 2006: 57-68
- [c48]Luis Rademacher, Santosh Vempala: Dispersion of Mass and the Complexity of Randomized Geometric Algorithms. FOCS 2006: 729-738
- [c47]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
- [c46]Amit Deshpande, Luis Rademacher, Santosh Vempala, Grant Wang: Matrix approximation and projective clustering via volume sampling. SODA 2006: 1117-1126
- [c45]
- [i5]Luis Rademacher, Santosh Vempala: Dispersion of Mass and the Complexity of Randomized Geometric Algorithms. CoRR abs/cs/0608054 (2006)
- [i4]Daniel Stefankovic, Santosh Vempala, Eric Vigoda: Adaptive Simulated Annealing: A Near-optimal Connection between Sampling and Counting. CoRR abs/cs/0612058 (2006)
- [i3]Amit Deshpande, Santosh Vempala: Adaptive Sampling and Fast Low-Rank Matrix Approximation. Electronic Colloquium on Computational Complexity (ECCC) 13(042) (2006)
- [i2]Luis Rademacher, Santosh Vempala: Dispersion of Mass and the Complexity of Randomized Geometric Algorithms. Electronic Colloquium on Computational Complexity (ECCC) 13(102) (2006)
- 2005
- [j21]Adam Tauman Kalai, Santosh Vempala: Efficient algorithms for online decision problems. J. Comput. Syst. Sci. 71(3): 291-307 (2005)
- [c44]Ravindran Kannan, Hadi Salmasian, Santosh Vempala: The Spectral Method for General Mixture Models. COLT 2005: 444-457
- [c43]
- [c42]David Cheng, Santosh Vempala, Ravi Kannan, Grant Wang: A divide-and-merge methodology for clustering. PODS 2005: 196-205
- [c41]Wenceslas Fernandez de la Vega, Marek Karpinski, Ravi Kannan, Santosh Vempala: Tensor decomposition and approximation schemes for constraint satisfaction problems. STOC 2005: 747-754
- 2004
- [j20]Ravi Kannan, Santosh Vempala, Adrian Vetta: On clusterings: Good, bad and spectral. J. ACM 51(3): 497-515 (2004)
- [j19]Dimitris Bertsimas, Santosh Vempala: Solving convex programs by random walks. J. ACM 51(4): 540-556 (2004)
- [j18]Alan M. Frieze, Ravi Kannan, Santosh Vempala: Fast monte-carlo algorithms for finding low-rank approximations. J. ACM 51(6): 1025-1041 (2004)
- [j17]John Dunagan, Santosh Vempala: Optimal outlier removal in high-dimensional spaces. J. Comput. Syst. Sci. 68(2): 335-373 (2004)
- [j16]Santosh Vempala, Grant Wang: A spectral algorithm for learning mixture models. J. Comput. Syst. Sci. 68(4): 841-860 (2004)
- [j15]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)
- [j14]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)
- [j13]
- [c40]Maria-Florina Balcan, Avrim Blum, Santosh Vempala: On Kernels, Margins, and Low-Dimensional Mappings. ALT 2004: 194-205
- [c39]
- [c38]
- [c37]John Dunagan, Santosh Vempala: A simple polynomial-time rescaling algorithm for solving linear programs. STOC 2004: 315-320
- [i1]Hadi Salmasian, Ravindran Kannan, Santosh Vempala: The Spectral Method for Mixture Models. Electronic Colloquium on Computational Complexity (ECCC)(067) (2004)
- 2003
- [j12]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)
- [c36]
- [c35]László Lovász, Santosh Vempala: Logconcave Functions: Geometry and Efficient Sampling Algorithms. FOCS 2003: 640-649
- [c34]László Lovász, Santosh Vempala: Simulated Annealing in Convex Bodies and an 0*(n4) Volume Algorithm. FOCS 2003: 650-659
- 2002
- [j11]Adam Kalai, Santosh Vempala: Efficient Algorithms for Universal Portfolios. Journal of Machine Learning Research 3: 423-440 (2002)
- [j10]Robert D. Carr, Santosh Vempala: Randomized metarounding. Random Struct. Algorithms 20(3): 343-352 (2002)
- [c33]Santosh Vempala, Grant Wang: A Spectral Algorithm for Learning Mixtures of Distributions. FOCS 2002: 113-
- [c32]
- [c31]
- [c30]Joseph Cheriyan, Santosh Vempala, Adrian Vetta: Approximation algorithms for minimum-cost k-vertex connected subgraphs. STOC 2002: 306-312
- 2001
- [j9]
- [c29]Joseph Cheriyan, Santosh Vempala: Edge Covers of Setpairs and the Iterative Rounding Method. IPCO 2001: 30-44
- [c28]Alantha Newman, Santosh Vempala: Fences Are Futile: On Relaxations for the Linear Ordering Problem. IPCO 2001: 333-347
- [c27]John Dunagan, Santosh Vempala: On Euclidean Embeddings and Bandwidth Minimization. RANDOM-APPROX 2001: 229-240
- [c26]
- 2000
- [j8]Christos H. Papadimitriou, Prabhakar Raghavan, Hisao Tamaki, Santosh Vempala: Latent Semantic Indexing: A Probabilistic Analysis. J. Comput. Syst. Sci. 61(2): 217-235 (2000)
- [j7]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)
- [c25]Santosh Vempala, Adrian Vetta: Factor 4/3 approximations for minimum 2-connected subgraphs. APPROX 2000: 262-273
- [c24]Ravi Kannan, Santosh Vempala, Adrian Vetta: On Clusterings - Good, Bad and Spectral. FOCS 2000: 367-377
- [c23]
- [c22]Robert D. Carr, Santosh Vempala, Jacques Mandler: Towards a 4/3 approximation for the asymmetric traveling salesman problem. SODA 2000: 116-125
- [c21]
- [c20]Christos H. Papadimitriou, Santosh Vempala: On the approximability of the traveling salesman problem (extended abstract). STOC 2000: 126-133
1990 – 1999
- 1999
- [j6]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)
- [j5]Ravi Kannan, Prasad Tetali, Santosh Vempala: Simple Markov-chain algorithms for generating bipartite graphs and tournaments. Random Struct. Algorithms 14(4): 293-308 (1999)
- [c19]Rosa I. Arriaga, Santosh Vempala: An Algorithmic Theory of Learning: Robust Concepts and Random Projection. FOCS 1999: 616-623
- [c18]
- [c17]Petros Drineas, Alan M. Frieze, Ravi Kannan, Santosh Vempala, V. Vinay: Clustering in Large Graphs and Matrices. SODA 1999: 291-299
- [c16]
- 1998
- [j4]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)
- [j3]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)
- [j2]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)
- [c15]Alan M. Frieze, Ravi Kannan, Santosh Vempala: Fast Monte-Carlo Algorithms for Finding Low-Rank Approximations. FOCS 1998: 370-378
- [c14]
- [c13]Christos H. Papadimitriou, Prabhakar Raghavan, Hisao Tamaki, Santosh Vempala: Latent Semantic Indexing: A Probabilistic Analysis. PODS 1998: 159-168
- [c12]Avrim Blum, Goran Konjevod, R. Ravi, Santosh Vempala: Semi-Definite Relaxations for Minimum Bandwidth and other Vertex-Ordering Problems. STOC 1998: 100-105
- 1997
- [j1]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)
- [c11]Santosh Vempala: A Random Sampling Based Algorithm for Learning the Intersection of Half-spaces. FOCS 1997: 508-513
- [c10]
- [c9]Ravi Kannan, Prasad Tetali, Santosh Vempala: Simple Markov-Chain Algorithms for Generating Bipartite Graphs and Tournaments (Extended Abstract). SODA 1997: 193-200
- [c8]Piotr Indyk, Rajeev Motwani, Prabhakar Raghavan, Santosh Vempala: Locality-Preserving Hashing in Multidimensional Spaces. STOC 1997: 618-625
- [c7]
- 1996
- [c6]Avrim Blum, Alan M. Frieze, Ravi Kannan, Santosh Vempala: A Polynomial-Time Algorithm for Learning Noisy Linear Threshold Functions. FOCS 1996: 330-338
- [c5]Avrim Blum, R. Ravi, Santosh Vempala: A Constant-factor Approximation Algorithm for the k MST Problem (Extended Abstract). STOC 1996: 442-448
- 1995
- [c4]Baruch Awerbuch, Yossi Azar, Avrim Blum, Santosh Vempala: Improved approximation guarantees for minimum-weight k-trees and prize-collecting salesmen. STOC 1995: 277-283
- [c3]Avrim Blum, Prasad Chalasani, Santosh Vempala: A constant-factor approximation for the k-MST problem in the plane. STOC 1995: 294-302
- 1994
- [c2]Vivek Arora, Santosh Vempala, Huzur Saran, Vijay V. Vazirani: A Limited-Backtrack Greedy Schema for Approximation Algorithms. FSTTCS 1994: 318-329
- 1993
- [c1]Naveen Garg, Santosh Vempala, Aman Singla: Improved Approximation Algorithms for Biconnected Subgraphs via Better Lower Bounding Techniques. SODA 1993: 103-111
Coauthor Index
data released under the ODC-BY 1.0 license. See also our legal information page
last updated on 2013-05-27 22:26 CEST by the dblp team