Ravi Kannan William K. Lanman Jr. Professor of Computer Science and Professor of Applied Mathematics Yale University

Research interests

• Theoretical Computer Science, Optimization
• Massive Data Sets, Sampling
• Clustering
• Markov Chains
• Linear Algebra Algorithms and Applications
• PORTIA project: Sensitive information in a wired world
  

Talks

Talk at the joint AMS-India conference, Bangalore, India, Dec. 2003.

Symposium on the Theory of Computing, 2005.

Conference on Learning Theory (COLT) 2005

Workshop on Modern Massive Data Sets, Stanford University, June 2006.

Vitae

My Vitae .

Publications

Massive Data, Sampling
• Tensor Decomposition and Approximation Algorithms for Constraint Satisfaction Problems
W. de la Vega, R. Kannan, M. Karpinski and S. Vempala, in the Proceedings of the Symposium on Theory of Computing (STOC) (2005).
• Random Sampling and approximation of MAX-CSPs
N. Alon, W. de la Vega, R. Kannan, M. Karpinski, in 34 th ACM STOC (2002) and final version in Journal of Computer and System Sciences 67 (2003) pp 212-243.
• Pass Efficient Algorithm for approximating large matrices,
P. Drineas and R. Kannan, in Symposium on Discrete Algorithms (SODA) (2003)
• Fast Monte Carlo Algorithms for Approximate Matrix Multiplication,
P. Drineas and R. Kannan, Proceedings of the Annual Symposium on the Foundations of Computing (2001)
• Fast Monte-Carlo Algorithms for finding low-rank approximations,
A. Frieze, R. Kannan and S. Vempala, Proceedings of the Foundations of Computer Science, 1998. pp 378-390
• Quick Approximation to Matrices and Applications,
A. Frieze and R. Kannan, Combinatorica 19 (2) (1999), 175-220.
• Fast Monte-Carlo Algorithms for Matrices,
P. Drineas, M. Mahoney and R. Kannan, Manuscripts (2003)
• Analyzing the structure of large graphs
R. Kannan and V. Vinay, Manuscript (1999)

Clustering
• A Divide-and- Merge methodology for Clustering
David Cheng, Ravi Kannan, Santosh Vempala and Grant Wang in ACM SIGMOD/PODS, 2005.
• Eigencluster : An Implementation of the Divide-and-Merge Methodology for Clustering
• A pass-efficient algorithm for clustering census data
Kevin Chang and R. Kannan, Manuscript.
• Learning Mixtures of separated non-spherical Gaussians
S. Arora and R. Kannan in the proceedings of the ACM Symposium on Theory of Computing (2001). Final Version submitted.
• On Clusterings : Good, bad and spectral
R. Kannan, S. Vempala and A. Vetta, in Proceedings of the Symposium on Foundations of Computer Science (2000). Final version to appear in Journal of the ACM.
• On a recursive spectral algorithm for clustering from pairwise similarities,
D. Cheng, R. Kannan and S. Vempala, Manuscript.
• Clustering in large graphs and matrices (conference version)
P. Drineas, A. Frieze, R. Kannan, S. Vempala, V. Vinay, in Symposium on Discrete Algorithms, SODA (1999)
• Clustering in large graphs via Singular Value Decomposition (Journal version)
P. Drineas, A. Frieze, R. Kannan, S. Vempala, V. Vinay, To Appear in Journal of Machine Learning. (2004)

Markov Chains, Rapid Mixing
• A random polynomial time algorithm for approximating the volume of convex sets
M. Dyer, A. Frieze and R. Kannan, in Journal of the Association for Computing Machinary, 38:1-17, (1991)
• Random walks and an O(n^5) time algorithm for volumes of convex sets
R. Kannan, L. Lovasz and M. Simonovits, in Random Structures and Algorithms, 11 (1997) 1-50.
• Markov Chains and polynomial time Algorithms,
R. Kannan, Plenary Talk, 35 th Annual IEEE Symnposium on the Foundatiuons of Computer Science, Sante Fe (1994)
• Rapid Mixing in Markov Chains
R. Kannan, Invited Talk, International Congresss of Mathematicians, Beijing, China, 2002
• Sampling and integration of near log-concave functions
D. Applegate and R. Kannan in Proceedings of the ACM Symposium on the Theory of Computing (1993)
• Isoperimetric problems for convex sets
R. Kannan, L. Lovasz and M. Simonovits, in Discrete and Computational Geometry 13:541-549 (1995)
• Log-Sobolev inequalities and sampling from log-concave densities
A. Frieze and R. Kannan in The Annals of Applied Probability, Vol. 9, No. 1, (1999) 14-26.
• Local search in smooth convex sets
R. Kannan and A. Nolte in Proceedings of the ACM Symposium on Theory of Computing (1998)
• A simple randomized algorithm for convex optimization
M. Dyer, R. Kannan and L. Stougie, Reports in Statistics, Probablity and Operations Research, Eindhoven University of Technology, The Netherlands (2001).
• Sampling Contingency tables
M. Dyer, R. Kannan and J. Mount, Random Structures and Algorithms, 10 487-506 (1997)
• Sampling according to the multivariate normal density
R. Kannan, G. Li, Proceedings of the Symposium on Foundations of Computer Science (1996)
• Sampling from log-concave distributions
A. Frieze, R. Kannan and N. Polson in the Annals of Applied Probability, Vol. 4, No. 3, (1994) 812-837
• Sampling Lattice points
R. Kannan and S. Vempala in Proceedings of the ACM Symposium on Theory of Computing (1997)
• Approximation of Radii and norm-maxima
A. Brieden, P. Gritzman, R. Kannan, V. Klee, L. Lovasz and M. Simonovits in Proceedings of the ACM Symposium on Theory of Computing (1998)
• Faster mixing via average conductance
L. Lovasz and R. Kannan, in Proceedings of the ACM Symposium on Theory of Computing (1999)
• Rapid Mixing of Several Markov Chains for a Hard-Core Model,
R. Kannan, M. W. Mahoney, and R. Montenegro, Proc. 14-th Annual ISAAC, 663-675. (2003).
• Blocking Conductance and Mixing in random walks,
R. Kannan, L. Lovasz and R. Montenegro, in Combinatorics, Probability and Computing (2005)

Lattice Algorithms
• Algorithmic Geometry of Numbers
R. Kannan in Annual Reviews of Computer Science eds., Traub, Grosz, Lampson and Nilsson, Vol. 2, (1987) pp 231-267, Publish. Annual Reviews Inc.

• Ravi Kannan William K. Lanman Jr. Professor of Computer Science and Professor of Applied Mathematics Yale University Research interests Theoretical Computer Science, Optimization Massive Data Sets, Sampling Clustering Markov Chains Linear Algebra Algorithms and Applications PORTIA project: Sensitive information in a wired world Talks Slides of Rosser Memorial Lecture, University of Wisconsin, Madison, Nov 12, 2002. Sampling on the fly Talk at the joint AMS-India conference, Bangalore, India, Dec. 2003. Randomized Algorithms in Linear Algebra Symposium on the Theory of Computing, 2005. Tensor Decomposition and Approximation algorithms for Max CSP's Conference on Learning Theory (COLT) 2005 The Spectral Method for general mixture models Workshop on Modern Massive Data Sets, Stanford University, June 2006. Sampling in large Matrices and Tensors Vitae My Vitae . Publications Massive Data, Sampling Tensor Decomposition and Approximation Algorithms for Constraint Satisfaction Problems W. de la Vega, R. Kannan, M. Karpinski and S. Vempala, in the Proceedings of the Symposium on Theory of Computing (STOC) (2005). Random Sampling and approximation of MAX-CSPs N. Alon, W. de la Vega, R. Kannan, M. Karpinski, in 34 th ACM STOC (2002) and final version in Journal of Computer and System Sciences 67 (2003) pp 212-243. Pass Efficient Algorithm for approximating large matrices, P. Drineas and R. Kannan, in Symposium on Discrete Algorithms (SODA) (2003) Fast Monte Carlo Algorithms for Approximate Matrix Multiplication, P. Drineas and R. Kannan, Proceedings of the Annual Symposium on the Foundations of Computing (2001) Fast Monte-Carlo Algorithms for finding low-rank approximations, A. Frieze, R. Kannan and S. Vempala, Proceedings of the Foundations of Computer Science, 1998. pp 378-390 Quick Approximation to Matrices and Applications, A. Frieze and R. Kannan, Combinatorica 19 (2) (1999), 175-220. Fast Monte-Carlo Algorithms for Matrices, P. Drineas, M. Mahoney and R. Kannan, Manuscripts (2003) Analyzing the structure of large graphs R. Kannan and V. Vinay, Manuscript (1999) Clustering A Divide-and- Merge methodology for Clustering David Cheng, Ravi Kannan, Santosh Vempala and Grant Wang in ACM SIGMOD/PODS, 2005. Eigencluster : An Implementation of the Divide-and-Merge Methodology for Clustering A pass-efficient algorithm for clustering census data Kevin Chang and R. Kannan, Manuscript. Learning Mixtures of separated non-spherical Gaussians S. Arora and R. Kannan in the proceedings of the ACM Symposium on Theory of Computing (2001). Final Version submitted. On Clusterings : Good, bad and spectral R. Kannan, S. Vempala and A. Vetta, in Proceedings of the Symposium on Foundations of Computer Science (2000). Final version to appear in Journal of the ACM. On a recursive spectral algorithm for clustering from pairwise similarities, D. Cheng, R. Kannan and S. Vempala, Manuscript. Clustering in large graphs and matrices (conference version) P. Drineas, A. Frieze, R. Kannan, S. Vempala, V. Vinay, in Symposium on Discrete Algorithms, SODA (1999) Clustering in large graphs via Singular Value Decomposition (Journal version) P. Drineas, A. Frieze, R. Kannan, S. Vempala, V. Vinay, To Appear in Journal of Machine Learning. (2004) Markov Chains, Rapid Mixing A random polynomial time algorithm for approximating the volume of convex sets M. Dyer, A. Frieze and R. Kannan, in Journal of the Association for Computing Machinary, 38:1-17, (1991) Random walks and an O(n^5) time algorithm for volumes of convex sets R. Kannan, L. Lovasz and M. Simonovits, in Random Structures and Algorithms, 11 (1997) 1-50. Markov Chains and polynomial time Algorithms, R. Kannan, Plenary Talk, 35 th Annual IEEE Symnposium on the Foundatiuons of Computer Science, Sante Fe (1994) Rapid Mixing in Markov Chains R. Kannan, Invited Talk, International Congresss of Mathematicians, Beijing, China, 2002 Sampling and integration of near log-concave functions D. Applegate and R. Kannan in Proceedings of the ACM Symposium on the Theory of Computing (1993) Isoperimetric problems for convex sets R. Kannan, L. Lovasz and M. Simonovits, in Discrete and Computational Geometry 13:541-549 (1995) Log-Sobolev inequalities and sampling from log-concave densities A. Frieze and R. Kannan in The Annals of Applied Probability, Vol. 9, No. 1, (1999) 14-26. Local search in smooth convex sets R. Kannan and A. Nolte in Proceedings of the ACM Symposium on Theory of Computing (1998) A simple randomized algorithm for convex optimization M. Dyer, R. Kannan and L. Stougie, Reports in Statistics, Probablity and Operations Research, Eindhoven University of Technology, The Netherlands (2001). Sampling Contingency tables M. Dyer, R. Kannan and J. Mount, Random Structures and Algorithms, 10 487-506 (1997) Sampling according to the multivariate normal density R. Kannan, G. Li, Proceedings of the Symposium on Foundations of Computer Science (1996) Sampling from log-concave distributions A. Frieze, R. Kannan and N. Polson in the Annals of Applied Probability, Vol. 4, No. 3, (1994) 812-837 Sampling Lattice points R. Kannan and S. Vempala in Proceedings of the ACM Symposium on Theory of Computing (1997) Approximation of Radii and norm-maxima A. Brieden, P. Gritzman, R. Kannan, V. Klee, L. Lovasz and M. Simonovits in Proceedings of the ACM Symposium on Theory of Computing (1998) Faster mixing via average conductance L. Lovasz and R. Kannan, in Proceedings of the ACM Symposium on Theory of Computing (1999) Rapid Mixing of Several Markov Chains for a Hard-Core Model, R. Kannan, M. W. Mahoney, and R. Montenegro, Proc. 14-th Annual ISAAC, 663-675. (2003). Blocking Conductance and Mixing in random walks, R. Kannan, L. Lovasz and R. Montenegro, in Combinatorics, Probability and Computing (2005) Lattice Algorithms Algorithmic Geometry of Numbers R. Kannan in Annual Reviews of Computer Science eds., Traub, Grosz, Lampson and Nilsson, Vol. 2, (1987) pp 231-267, Publish. Annual Reviews Inc. Lattice Translates of a polytope and the Frobenius problem R. Kannan in Combinatorica, 12 (2) (1992) pp 161-177. Test sets for Integer Programs and ``forall there exist'' sentences R. Kannan, Dimacs Series in Discrete Mathematics and Theoretical Computer Science, Vol 1., (1990) pp 39-47, Publish. Americal Mathematical Society. On integer points in a polyhedron W. Cook, M. Hartman, R. Kannan and C. Mcdiarmid, in Combinatorica 12 (1) (1992). Contact information Ravi Kannan Department of Computer Science Yale University New Haven, CT 06520 Telephone: 203.432.1228 Fax: 203.432.XXXX Email: kannan@cs.yale.edu