Santosh Vempala's papers (in ps/pdf) on Algorithms, Randomness, Geometry and Combinatorics.

1. Isotropic PCA and Affine-Invariant Clustering (S.C. Brubaker) [conf version]
   Building Bridges (Ed.s M. Gr\"{o}tchel and G.O.H.Katona), Bolyai Society Mathematical Studies, 2008. (special issue in honor of Laci Lovasz).
   Proc. of FOCS 2008.
   
2. Path Splicing (M. Motiwala, M. Elmore and N. Feamster)
   Proc. of SIGCOMM, 2008.
   
3. Logconcave Random Graphs (A. Frieze and J. Vera)
   Proc. of STOC 2008.
   
4. A Discriminative Framework for Clustering via Similarity Functions (M. F. Balcan and A. Blum)
   Proc. of STOC, 2008.
   
5. Life (and Routing) on the Wireless Manifold (V. Kanade)
   Proc. of HotNets, 2007.
   
6. Path Splicing: Reliable Connectivity with Rapid Recovery (M. Motiwala and N. Feamster)
   Proc. of HotNets, 2007.
   
7. Filtering Spam with Behavioral Blacklisting (A. Ramachandran and N. Feamster)
   Proc. ACM Computer and Communication Security, 2007.
   
8. Adaptive Simulated Annealing: A Near-optimal Connection between Sampling and Counting (D. Stefankovic and E. Vigoda)
   Proc. of the 48th IEEE Symposium on Foundations of Computer Science (FOCS '07), 2007.
   (invited to special issue)
9. An Efficient Re-scaled Perceptron Algorithm for Conic Systems (A. Belloni, R. Freund)
   Proc. of 20th Conf. on Computational Learning Theory, San Diego, 2007.
   
10. Dispersion of Mass and the Complexity of Randomized Geometric Algorithms (L. Rademacher)
    Proc. of the 47th IEEE Symposium on Foundations of Computer Science (FOCS '06), 2006.
    To appear in Advances in Mathematics.
11. Fast Algorithms for Logconcave Functions: Sampling, Rounding, Integration and Optimization (L. Lovasz)
    Proc. of the 47th IEEE Symposium on Foundations of Computer Science (FOCS '06), 2006.
    
12. Adaptive Sampling and Fast Low-rank Matrix Approximation (A. Deshpande)
    Proc. of RANDOM, 2006.
    
13. Symmetric Network Computation (D. Pritchard)
    Proc. of ACM SPAA, 2006.
    
14. Matrix Approximation and Projective Clustering via Volume Sampling (A. Deshpande, L. Rademacher and G. Wang)
    Proc. of the 17th ACM-SIAM Symposium on Discrete Algorithms, 2006.
    Theory of Computing, 2006
    
15. Local versus Global Properties of Metric Spaces (S. Arora, L. Lovasz, I. Newman, Y. Rabani and Y. Rabinovich)
    Proc. of the 17th ACM-SIAM Symposium on Discrete Algorithms, 2006.
    
16. Nash Equilibria in Random Games (I. Barany and A. Vetta)
    Proc. of the 46th IEEE Symposium on Foundations of Computer Science (FOCS '05), 2005. (invited to special issue)
    Random Structures and Algorithms, 2007.
17. The spectral method for general mixture models (R. Kannan and H. Salmasian)
    Proc. of the 18th Conference on Learning Theory, 2005 (Mark Fulk award).
    
18. A Divide-and-Merge Methodology for Clustering (D. Cheng, R. Kannan and G. Wang)
    Proc. of the ACM Symposium on Principles of Database Systems, 2005.
    ACM Trans. Database Systems, 2006.
    
19. Tensor decomposition and approximation schemes for constraint satisfaction problems.
    (W. F. de la Vega, R. Kannan and M. Karpinski)
    Proc. of the 37th ACM Symposium on the Theory of Computing (STOC '05), 2005.
    
20. Geometric Random Walks: A Survey.
    MSRI volume on Combinatorial and Computational Geometry.
    
21. Testing geometric convexity. (Luis Rademacher)
    Proc. of the 24th FST & TCS, Chennai, 2004.
    
22. On Kernels, Margins and Low-dimensional Mappings. (Nina Balcan, Avrim Blum)
    Proc. of the 15th Conf. Algorithmic Learning Theory, Padua, 2004.
    Machine Learning
    
23. Hit-and-run from a corner. (László Lovász)
    Proc. of the 36th ACM Symposium on the Theory of Computing (STOC '04), Chicago, 2004.
    SIAM J. Computing (STOC04 special issue).
    
24. A simple polynomial-time rescaling algorithm for solving linear programs.(John Dunagan)
    Proc. of the 36th ACM Symposium on the Theory of Computing (STOC '04), Chicago, 2004.
    Math. Prog. A
    
25. Simulated annealing in convex bodies and an O*(n^4) volume algorithm. (László Lovász)
    Proc. of the 44th IEEE Foundations of Computer Science (FOCS '03), Boston, 2003.
    JCSS (FOCS03 special issue).
    
26. Simulated annealing for convex optimization . (Adam Kalai)
    Math of OR.
    
27. Logconcave functions: Geometry and efficient sampling algorithms. (László Lovász)
    Proc. of the 44th IEEE Foundations of Computer Science (FOCS '03), Boston, 2003.
    Random Structures and Algorithms
28. Efficient algorithms for the online decision problem. (Adam Kalai)
    Proc. of 16th Conf. on Computational Learning Theory, Washington D.C., 2003.
    
29. A spectral algorithm for learning mixtures of distributions. (Grant Wang)
    Proc. of the 43rd IEEE Foundations of Computer Science (FOCS '02), Vancouver, 2002.
    JCSS (special issue for FOCS '02), 68(4), 841--860, 2004.
    
30. Solving convex programs by random walks. (Dimitris Bertsimas)
    Journal of the ACM (JACM) 51(4), 540--556, 2004.
    Proc. of the 34th ACM Symposium on the Theory of Computing (STOC '02), Montreal, 2002.
    
31. An approximation algorithm for the minimum-cost k-vertex connected subgraph.
    (Joseph Cheriyan, Adrian Vetta)
    SIAM J. Computing, 32(4) (2003), 1050-1055.
    
32. Network design via iterative rounding of setpair relaxations. (Joseph Cheriyan, Adrian Vetta)
    Combinatorica.
    A preliminary version of the previous two appeared as
    Approximation algorithms for minimum-cost k-connected subgraphs.
    Proc. of the 34th ACM Symposium on the Theory of Computing (STOC '02), Montreal, 2002.
    
33. Flow metrics. (Claudson Bornstein)
    Proc. of the 5th Symposium on Latin American Theoretical Informatics, Cancun, 2002.
    Theoretical Computer Science (special issue for LATIN '02), 321(1), 13--24, 2004.
    
34. On Euclidean embeddings and bandwidth minimization. (John Dunagan)
    Proc. of the 5th Workshop on Randomization and Approximation, Berkeley, 2001.
    
35. Optimal outlier removal in high-dimensional spaces. (John Dunagan)
    Proc. of the 33rd ACM Symposium on the Theory of Computing (STOC '01), Crete, 2001.
    JCSS (special issue for STOC '01), 68(2), 335--373, 2004.
    
36. Edge covers of setpairs and the iterative rounding method. (Joseph Cheriyan)
    Proc. of Integer Programming and Combinatorial Optimization, Utrecht, 2001.
37. Fences are futile: on relaxations for the linear ordering problem. (Alantha Newman)
    Proc. of Integer Programming and Combinatorial Optimization, Utrecht, 2001.
38. On clusterings: good, bad and spectral. (Ravi Kannan and Adrian Vetta)
    Journal of the ACM (JACM) 51(3), 497--515, 2004.
    Proc. of the 41st Foundations of Computer Science (FOCS '00), Redondo Beach, 2000.
    
39. Efficient algorithms for universal portfolios. (Adam Kalai)
    J. Machine Learning Research, 3, (2002), 423--440 (invited).
    Proc. of the 41st Foundations of Computer Science (FOCS '00), Redondo Beach, 2000.
    
40. Factor 4/3 approximations for minimum 2-connected subgraphs. (Adrian Vetta)
    Proc. of the 3rd Workshop on Approximation , Saarbrucken, 2000.
    
41. On the approximability of the traveling salesman problem. (Christos H. Papadimitriou)
    Proc. of the 32nd ACM Symposium on the Theory of Computing (STOC '00), Portland, 2000.
    To appear in Combinatorica.
    
42. Randomized meta-rounding. (Bob Carr)
    Random Structures and Algorithms, 20(3), (2002), 343-352 (invited).
    Proc. of the 32nd ACM Symposium on the Theory of Computing (STOC '00), Portland, 2000.
    
43. On the Held-Karp relaxation for the asymmetric and symmetric TSPs. (Bob Carr)
    Proc. of the 11th ACM-SIAM Symposium on Discrete Algorithms , San Francisco, 2000.
    Mathematical Programming, 100(3), 569--587, 2004.
    
44. Approximating multicast congestion. (Berthold Vocking)
    Proc. of ISAAC, Chennai, 1999.
    
45. An algorithmic theory of learning: Robust Concepts and Random Projection. (Rosa I. Arriaga)
    Proc. of the 40th Foundations of Computer Science (FOCS '99), New York, 1999.
    To appear in Machine Learning.
46. A convex relaxation for the Asymmetric TSP. (Mihalis Yannakakis)[two pages only]
    Proc. of the 10th ACM-SIAM Symposium on Discrete Algorithms, Baltimore, 1999.
    
47. Clustering large graphs via the Singular Value Decomposition. (Petros Drineas, Ravi Kannan, Alan Frieze and V. Vinay)
    Machine Learning 56, 9--33, 2004.
    Proc. of the 10th ACM-SIAM Symposium on Discrete Algorithms, Baltimore, 1999.
    
48. Random Projection: A New Approach to VLSI Layout.
    Proc. of the 39th Foundations of Computer Science (FOCS '98), Palo Alto, 1998.
    
49. Fast Monte-Carlo Algorithms for Finding Low-Rank Approximations. (A. Frieze, R. Kannan)
    Proc. of the 39th Foundations of Computer Science (FOCS '98), Palo Alto, 1998.
    Journal of the ACM (JACM), 51(6), 1025-1041, 2004.
    
50. Semi-Definite Relaxations for Minimum Bandwidth and other Vertex-Ordering Problems.
    (Avrim Blum, Goran Konjevod and R. Ravi)
    Proc. of the 30th ACM Symposium on the Theory of Computing (STOC '98), Dallas, 1998.
    Theoretical Computer Science, 235 (2000), 25-42 (special issue in honour of Manuel Blum).
    
51. A Random Sampling based Algorithm for learning the Intersection of Half-spaces
    Proc. of the 38th Foundations of Computer Science (FOCS '97), Miami, 1997. (Machtey Prize)
    
52. Sampling Lattice Points. (Ravi Kannan)
    Proc. 29th ACM Symposium on the Theory of Computing (STOC '97), El Paso, 1997.
    Invited for publication in Journal of Comp. and System Sciences.
    
53. Locality-Preserving Hashing in Multidimensional Spaces.
    (Piotr Indyk, Rajeev Motwani and Prabhakar Raghavan)
    Proc. 29th ACM Symposium on the Theory of Computing (STOC '97), El Paso, 1997.
    
54. Latent Semantic Indexing: A Probabilistic Analysis.
    (Christos Papadimitriou, Prabhakar Raghavan and Hisao Tamaki)
    Proc. 17th ACM Symposium on the Principles of Database Systems, Seattle, 1998.
    Journal of Comp. and System Sciences (special issue for PODS '01), 61, 2000 217-235.
    
55. Simple Markov-Chain Algorithms for Generating Bipartite Graphs and Tournaments.
    (Ravi Kannan and Prasad Tetali)
    Proc. 8th ACM-SIAM Symposium on Discrete Algorithms, New Orleans, 1997.
    Random Structures and Algorithms, 14(4), 1999, 293-308.
    
56. A Polynomial-Time Algorithm for Learning Noisy Linear Threshold Functions.
    (Avrim Blum, Alan Frieze and Ravi Kannan)
    Proc. 37th IEEE Symposium on the Foundations of Computer Science (FOCS '96), Burlington, 1996.
    Algorithmica, 22(1), 35-52 (invited).
    
57. The Colin de Verdičre Number and Sphere Representations of a Graph
    (Andrew Kotlov and László Lovász)
    Combinatorica, 17(4), 1997.
    
58. A Constant-Factor Approximation for the k-MST Problem. (Avrim Blum, R. Ravi)
    Proc. 28th ACM Symposium on the Theory of Computing (STOC '96), Philadelphia, 1996.
    J. Computer and System Sciences, 58(1), 101-108 (special issue for STOC '96).
    
59. Improved Approximations for Minimum-Weight k-Trees and Prize-Collecting Salesmen.
    (Baruch Awerbuch, Yossi Azar, Avrim Blum)
    Proc. 27th ACM Symposium on the Theory of Computing (STOC '95), Las Vegas, 1995.
    SIAM J. on Computing, 28(1) 1999.
    
60. A Constant-Factor Approximation for the k-MST Problem in the Plane. (A. Blum, P. Chalasani)
    Proc. 27th ACM Symposium on the Theory of Computing (STOC '95), Las Vegas, 1995.
    A Constant-Factor Approximation Algorithm for the Geometric k-MST Problem in the Plane
    (J.S.B. Mitchell, A. Blum, P. Chalasani)
    Siam J. on Computing , 28(3) 1999.
    
61. Improved Approximations for Finding Minimum 2-connected Subgraphs via Better Lower-Bounding Techniques
    (Naveen Garg, Aman Singla)
    Proc. 4th ACM-SIAM Symposium on Discrete Algorithms, Austin, 1993.
62. Vivek Arora, Huzur Saran, Vijay Vazirani and Santosh Vempala,
    ``A Limited-Backtrack Greedy Schema for Approximation Algorithms,''
    Proc. 14th Conf. on the Foundations of Software Technology and Theoretical Computer Science, Madras, 1994.