default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDRavi Kannan
Ravindran Kannan
Person information
- affiliation: Yale University, New Haven, Connecticut, USA
- award (2011): Knuth Prize
- award (1991): Fulkerson Prize
Refine list
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
showing all ?? records
2020 – today
- 2024
[c70]Chiranjib Bhattacharyya, Ravindran Kannan, Amit Kumar:
Random Separating Hyperplane Theorem and Learning Polytopes. ICALP 2024: 25:1-25:20- [i20]Ravindran Kannan, Chiranjib Bhattacharyya, Praneeth Kacham, David P. Woodruff:
LevAttention: Time, Space, and Streaming Efficient Algorithm for Heavy Attentions. CoRR abs/2410.05462 (2024) - 2023
- [c69]Papri Dey, Ravi Kannan, Nick Ryder, Nikhil Srivastava:
Bit Complexity of Jordan Normal Form and Polynomial Spectral Factorization. ITCS 2023: 42:1-42:18 - [i19]Chiranjib Bhattacharyya, Ravindran Kannan, Amit Kumar:
Random Separating Hyperplane Theorem and Learning Polytopes. CoRR abs/2307.11371 (2023) - 2022
- [c68]Chiranjib Bhattacharyya, Ravindran Kannan, Amit Kumar:
How many Clusters? - An algorithmic answer. SODA 2022: 2607-2640 - 2021
- [j55]Ravindran Kannan
, Narender Singh, Andrzej Przekwas, Xianlian Zhou, Ross Walenga, Andrew Babiskin:
A quasi-3D model of the whole lung: airway extension to the tracheobronchial limit using the constrained constructive optimization and alveolar modeling, using a sac-trumpet model. J. Comput. Des. Eng. 8(2): 691-704 (2021) - [c67]Ainesh Bakshi, Chiranjib Bhattacharyya, Ravi Kannan, David P. Woodruff, Samson Zhou:
Learning a Latent Simplex in Input Sparsity Time. ICLR 2021 - [c66]Chiranjib Bhattacharyya, Ravindran Kannan, Amit Kumar:
Finding k in Latent k- polytope. ICML 2021: 894-903 - [i18]Ainesh Bakshi, Chiranjib Bhattacharyya, Ravi Kannan, David P. Woodruff, Samson Zhou:
Learning a Latent Simplex in Input-Sparsity Time. CoRR abs/2105.08005 (2021) - [i17]Papri Dey, Ravi Kannan, Nick Ryder, Nikhil Srivastava:
Bit Complexity of Jordan Normal Form and Spectral Factorization. CoRR abs/2109.13956 (2021) - 2020
- [c65]Chiranjib Bhattacharyya, Ravindran Kannan:
Near-optimal sample complexity bounds for learning Latent k-polytopes and applications to Ad-Mixtures. ICML 2020: 854-863 - [c64]Chiranjib Bhattacharyya, Ravindran Kannan:
Finding a latent k-simplex in O* (k · nnz(data)) time via Subset Smoothing. SODA 2020: 122-140 - [i16]Chiranjib Bhattacharyya, Ravindran Kannan, Amit Kumar:
Algorithms for finding k in k-means. CoRR abs/2012.04388 (2020)
2010 – 2019
- 2019
- [i15]Chiranjib Bhattacharyya, Ravindran Kannan:
Finding a latent k-simplex in O(k . nnz(data)) time via Subset Smoothing. CoRR abs/1904.06738 (2019) - 2017
- [j54]Ravindran Kannan, Santosh S. Vempala:
Randomized algorithms in numerical linear algebra. Acta Numer. 26: 95-135 (2017) - [c63]Ravindran Kannan, Santosh S. Vempala:
The Hidden Hubs Problem. COLT 2017: 1190-1213 - 2016
- [j53]Sanjeev Arora, Rong Ge, Ravi Kannan, Ankur Moitra:
Computing a Nonnegative Matrix Factorization - Provably. SIAM J. Comput. 45(4): 1582-1611 (2016) - [c62]Chiranjib Bhattacharyya, Navin Goyal, Ravindran Kannan, Jagdeep Pani:
Non-negative Matrix Factorization under Heavy Noise. ICML 2016: 1426-1434 - [i14]Ravi Kannan, Santosh S. Vempala:
Beyond Spectral: Tight Bounds for Planted Gaussians. CoRR abs/1608.03643 (2016) - [i13]Ravindran Kannan, Michael W. Mahoney, David P. Woodruff:
Recent Advances in Randomized Numerical Linear Algebra (NII Shonan Meeting 2016-10). NII Shonan Meet. Rep. 2016 (2016) - 2015
- [c61]Jugal Garg, Ravi Kannan:
Markets with Production: A Polynomial Time Algorithm and a Reduction to Pure Exchange. EC 2015: 733-749 - 2014
- [j52]Martin E. Dyer, Ravi Kannan, Leen Stougie:
A simple randomised algorithm for convex optimisation - Application to two-stage stochastic programming. Math. Program. 147(1-2): 207-229 (2014) - [j51]Ravindran Kannan:
14th Knuth prize: call for nominations. SIGACT News 45(1): 7-8 (2014) - [c60]Ravi Kannan, Santosh S. Vempala, David P. Woodruff:
Principal Component Analysis and Higher Correlations for Distributed Data. COLT 2014: 1040-1057 - [c59]Amirali Abdullah, Alexandr Andoni, Ravindran Kannan, Robert Krauthgamer:
Spectral Approaches to Nearest Neighbor Search. FOCS 2014: 581-590 - [c58]Trapit Bansal, Chiranjib Bhattacharyya, Ravindran Kannan:
A provable SVD-based algorithm for learning topics in dominant admixture corpus. NIPS 2014: 1997-2005 - [i12]Amirali Abdullah, Alexandr Andoni, Ravindran Kannan, Robert Krauthgamer:
Spectral Approaches to Nearest Neighbor Search. CoRR abs/1408.0751 (2014) - [i11]Trapit Bansal, Chiranjib Bhattacharyya, Ravindran Kannan:
A provable SVD-based algorithm for learning topics in dominant admixture corpus. CoRR abs/1410.6991 (2014) - 2013
- [i10]Ravindran Kannan, Santosh S. Vempala:
Nimble Algorithms for Cloud Computing. CoRR abs/1304.3162 (2013) - 2012
- [j50]Ravindran Kannan, Hariharan Narayanan:
Random Walks on Polytopes and an Affine Interior Point Method for Linear Programming. Math. Oper. Res. 37(1): 1-20 (2012) - [c57]Amit Deshpande, Ravindran Kannan, Nikhil Srivastava:
Zero-One Rounding of Singular Vectors. ICALP (1) 2012: 278-289 - [c56]Sanjeev Arora, Rong Ge, Ravindran Kannan, Ankur Moitra:
Computing a nonnegative matrix factorization - provably. STOC 2012: 145-162 - 2011
- [j49]Ravi Kannan:
Algorithms: Recent Highlights and Challenges. SIGARCH Comput. Archit. News 39(3) (2011) - [i9]Sanjeev Arora, Rong Ge, Ravi Kannan, Ankur Moitra:
Computing a Nonnegative Matrix Factorization -- Provably. CoRR abs/1111.0952 (2011) - 2010
- [c55]Amit Kumar, Ravindran Kannan:
Clustering with Spectral Norm and the k-Means Algorithm. FOCS 2010: 299-308 - [c54]Ravindran Kannan:
Spectral methods for matrices and tensors. STOC 2010: 1-12 - [i8]Ravindran Kannan:
Spectral Methods for Matrices and Tensors. CoRR abs/1004.1253 (2010) - [i7]Amit Kumar, Ravindran Kannan:
Clustering with Spectral Norm and the k-means Algorithm. CoRR abs/1004.1823 (2010)
2000 – 2009
- 2009
- [j48]Ravi Kannan, Santosh S. Vempala:
Spectral Algorithms. Found. Trends Theor. Comput. Sci. 4(3-4): 157-288 (2009) - [j47]Ravi Kannan, Luis Rademacher:
Optimization of a convex program with a polynomial perturbation. Oper. Res. Lett. 37(6): 384-386 (2009) - [j46]Kevin L. Chang, Ravi Kannan:
Pass-Efficient Algorithms for Learning Mixtures of Uniform Distributions. SIAM J. Comput. 39(3): 783-812 (2009) - [c53]Ankit Aggarwal, Amit Deshpande, Ravi Kannan:
Adaptive Sampling for k-Means Clustering. APPROX-RANDOM 2009: 15-28 - [c52]Animesh Mukherjee, Monojit Choudhury, Ravi Kannan:
Discovering Global Patterns in Linguistic Networks through Spectral Analysis: A Case Study of the Consonant Inventories. EACL 2009: 585-593 - [c51]Ravindran Kannan:
A New Probability Inequality Using Typical Moments and Concentration Results. FOCS 2009: 211-220 - [c50]Ravi Kannan, K. Narayan Kumar:
Preface -- IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (2009). FSTTCS 2009 - [c49]Ravi Kannan, Hariharan Narayanan:
Random walks on polytopes and an affine interior point method for linear programming. STOC 2009: 561-570 - [c48]Atish Das Sarma, Amit Deshpande, Ravi Kannan:
Finding Dense Subgraphs in G(n, 1/2). WAOA 2009: 98-103 - [e3]Ravi Kannan, K. Narayan Kumar:
IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2009, December 15-17, 2009, IIT Kanpur, India. LIPIcs 4, Schloss Dagstuhl - Leibniz-Zentrum für Informatik 2009, ISBN 978-3-939897-13-2 [contents] - [i6]Animesh Mukherjee, Monojit Choudhury, Ravi Kannan:
Discovering Global Patterns in Linguistic Networks through Spectral Analysis: A Case Study of the Consonant Inventories. CoRR abs/0901.2216 (2009) - 2008
- [j45]Petros Drineas, Ravi Kannan, Michael W. Mahoney:
Sampling subproblems of heterogeneous Max-Cut problems and approximation algorithms. Random Struct. Algorithms 32(3): 307-333 (2008) - [j44]Ravindran Kannan, Hadi Salmasian, Santosh S. Vempala:
The Spectral Method for General Mixture Models. SIAM J. Comput. 38(3): 1141-1156 (2008) - [c47]Nikhil R. Devanur, Ravi Kannan:
Market Equilibria in Polynomial Time for Fixed Number of Goods or Agents. FOCS 2008: 45-53 - [c46]Alan M. Frieze, Ravi Kannan:
A new approach to the planted clique problem. FSTTCS 2008: 187-198 - [i5]Atish Das Sarma, Amit Deshpande, Ravi Kannan:
Finding Dense Subgraphs in G(n,1/2). CoRR abs/0807.5111 (2008) - 2007
- [c45]Anirban Dasgupta, John E. Hopcroft, Ravi Kannan, Pradipta Prometheus Mitra:
Spectral clustering with limited independence. SODA 2007: 1036-1045 - [c44]Ravi Kannan, Thorsten Theobald:
Games of fixed rank: a hierarchy of bimatrix games. SODA 2007: 1124-1132 - 2006
- [j43]Ravi Kannan, László Lovász, Ravi Montenegro:
Blocking Conductance and Mixing in Random Walks. Comb. Probab. Comput. 15(4): 541-570 (2006) - [j42]Petros Drineas, Ravi Kannan, Michael W. Mahoney:
Fast Monte Carlo Algorithms for Matrices I: Approximating Matrix Multiplication. SIAM J. Comput. 36(1): 132-157 (2006) - [j41]Petros Drineas, Ravi Kannan, Michael W. Mahoney:
Fast Monte Carlo Algorithms for Matrices II: Computing a Low-Rank Approximation to a Matrix. SIAM J. Comput. 36(1): 158-183 (2006) - [j40]Petros Drineas, Ravi Kannan, Michael W. Mahoney:
Fast Monte Carlo Algorithms for Matrices III: Computing a Compressed Approximate Matrix Decomposition. SIAM J. Comput. 36(1): 184-206 (2006) - [j39]David Cheng, Ravi Kannan, Santosh S. Vempala, Grant Wang:
A divide-and-merge methodology for clustering. ACM Trans. Database Syst. 31(4): 1499-1525 (2006) - [c43]Anirban Dasgupta, John E. Hopcroft, Ravi Kannan, Pradipta Prometheus Mitra:
Spectral Clustering by Recursive Partitioning. ESA 2006: 256-267 - [c42]Kevin L. Chang, Ravi Kannan:
The space complexity of pass-efficient algorithms for clustering. SODA 2006: 1157-1166 - [i4]Wenceslas Fernandez de la Vega, Ravi Kannan, Marek Karpinski:
Approximation of Global MAX-CSP Problems. Electron. Colloquium Comput. Complex. TR06 (2006) - 2005
- [c41]Ravindran Kannan, Hadi Salmasian, Santosh S. Vempala:
The Spectral Method for General Mixture Models. COLT 2005: 444-457 - [c40]David Cheng, Santosh S. Vempala, Ravi Kannan, Grant Wang:
A divide-and-merge methodology for clustering. PODS 2005: 196-205 - [c39]Petros Drineas, Ravi Kannan, Michael W. Mahoney:
Sampling Sub-problems of Heterogeneous Max-cut Problems and Approximation Algorithms. STACS 2005: 57-68 - [c38]Wenceslas Fernandez de la Vega, Marek Karpinski, Ravi Kannan, Santosh S. Vempala:
Tensor decomposition and approximation schemes for constraint satisfaction problems. STOC 2005: 747-754 - [i3]Ravi Kannan, Thorsten Theobald:
Games of fixed rank: A hierarchy of bimatrix games. CoRR abs/cs/0511021 (2005) - 2004
- [j38]Ravi Kannan, Santosh S. Vempala, Adrian Vetta:
On clusterings: Good, bad and spectral. J. ACM 51(3): 497-515 (2004) - [j37]Alan M. Frieze, Ravi Kannan, Santosh S. Vempala:
Fast monte-carlo algorithms for finding low-rank approximations. J. ACM 51(6): 1025-1041 (2004) - [j36]Petros Drineas, Alan M. Frieze, Ravi Kannan, Santosh S. Vempala, V. Vinay:
Clustering Large Graphs via the Singular Value Decomposition. Mach. Learn. 56(1-3): 9-33 (2004) - [i2]Hadi Salmasian, Ravindran Kannan, Santosh S. Vempala:
The Spectral Method for Mixture Models. Electron. Colloquium Comput. Complex. TR04 (2004) - 2003
- [j35]Noga Alon, Wenceslas Fernandez de la Vega, Ravi Kannan, Marek Karpinski:
Random sampling and approximation of MAX-CSPs. J. Comput. Syst. Sci. 67(2): 212-243 (2003) - [c37]Ravi Kannan, Michael W. Mahoney, Ravi Montenegro:
Rapid Mixing of Several Markov Chains for a Hard-Core Model. ISAAC 2003: 663-675 - [c36]Petros Drineas, Ravi Kannan:
Pass efficient algorithms for approximating large matrices. SODA 2003: 223-232 - 2002
- [j34]Evgeny Dantsin, Andreas Goerdt, Edward A. Hirsch, Ravi Kannan, Jon M. Kleinberg, Christos H. Papadimitriou, Prabhakar Raghavan, Uwe Schöning:
A deterministic (2-2/(k+1))n algorithm for k-SAT based on local search. Theor. Comput. Sci. 289(1): 69-83 (2002) - [c35]Noga Alon, Wenceslas Fernandez de la Vega, Ravi Kannan, Marek Karpinski:
Random sampling and approximation of MAX-CSP problems. STOC 2002: 232-239 - 2001
- [c34]Petros Drineas, Ravi Kannan:
Fast Monte-Carlo Algorithms for Approximate Matrix Multiplication. FOCS 2001: 452-459 - [c33]Sanjeev Arora, Ravi Kannan:
Learning mixtures of arbitrary gaussians. STOC 2001: 247-257 - [i1]Noga Alon, Wenceslas Fernandez de la Vega, Ravi Kannan, Marek Karpinski:
Random Sampling and Approximation of MAX-CSP Problems. Electron. Colloquium Comput. Complex. TR01 (2001) - 2000
- [c32]Ravi Kannan, Santosh S. Vempala, Adrian Vetta:
On Clusterings - Good, Bad and Spectral. FOCS 2000: 367-377
1990 – 1999
- 1999
- [j33]Alan M. Frieze, Ravi Kannan:
Quick Approximation to Matrices and Applications. Comb. 19(2): 175-220 (1999) - [j32]Alan M. Frieze, Ravi Kannan:
A Simple Algorithm for Constructing Szemere'di's Regularity Partition. Electron. J. Comb. 6 (1999) - [j31]Ravi Kannan, Prasad Tetali, Santosh S. Vempala:
Simple Markov-chain algorithms for generating bipartite graphs and tournaments. Random Struct. Algorithms 14(4): 293-308 (1999) - [c31]Petros Drineas, Alan M. Frieze, Ravi Kannan, Santosh S. Vempala, V. Vinay:
Clustering in Large Graphs and Matrices. SODA 1999: 291-299 - [c30]László Lovász, Ravi Kannan:
Faster Mixing via Average Conductance. STOC 1999: 282-287 - 1998
- [j30]Avrim Blum, Alan M. Frieze, Ravi Kannan, Santosh S. Vempala:
A Polynomial-Time Algorithm for Learning Noisy Linear Threshold Functions. Algorithmica 22(1/2): 35-52 (1998) - [c29]Ravi Kannan, Andreas Nolte:
A Fast Random Greedy Algorithm for the Component Commonality Problem. ESA 1998: 223-234 - [c28]Ravi Kannan, Andreas Nolte:
Local Search in Smooth Convex Sets. FOCS 1998: 218-226 - [c27]Andreas Brieden, Peter Gritzmann, Ravi Kannan, Victor Klee, László Lovász, Miklós Simonovits:
Approximation of Diameters: Randomization Doesn't Help. FOCS 1998: 244-251 - [c26]Alan M. Frieze, Ravi Kannan, Santosh S. Vempala:
Fast Monte-Carlo Algorithms for Finding Low-Rank Approximations. FOCS 1998: 370-378 - 1997
- [j29]Avrim Blum, Ravindran Kannan:
Learning an Intersection of a Constant Number of Halfspaces over a Uniform Distribution. J. Comput. Syst. Sci. 54(2): 371-380 (1997) - [j28]Martin E. Dyer, Ravi Kannan:
On Barvinok's Algorithm for Counting Lattice Points in Fixed Dimension. Math. Oper. Res. 22(3): 545-549 (1997) - [j27]Martin E. Dyer, Ravi Kannan, John Mount:
Sampling contingency tables. Random Struct. Algorithms 10(4): 487-506 (1997) - [j26]Ravi Kannan, László Lovász, Miklós Simonovits:
Random walks and an O*(n5) volume algorithm for convex bodies. Random Struct. Algorithms 11(1): 1-50 (1997) - [c25]Ravi Kannan, Prasad Tetali, Santosh S. Vempala:
Simple Markov-Chain Algorithms for Generating Bipartite Graphs and Tournaments (Extended Abstract). SODA 1997: 193-200 - [c24]Ravi Kannan, Santosh S. Vempala:
Sampling Lattice Points. STOC 1997: 696-700 - 1996
- [c23]Alan M. Frieze, Ravi Kannan:
The Regularity Lemma and Approximation Schemes for Dense Problems. FOCS 1996: 12-20 - [c22]Ravi Kannan, Guangxing Li:
Sampling According to the Multivariate Normal Density. FOCS 1996: 204-212 - [c21]Avrim Blum, Alan M. Frieze, Ravi Kannan, Santosh S. Vempala:
A Polynomial-Time Algorithm for Learning Noisy Linear Threshold Functions. FOCS 1996: 330-338 - [c20]Alan M. Frieze, Mark Jerrum, Ravi Kannan:
Learning Linear Transformations. FOCS 1996: 359-368 - 1995
- [j25]Ravi Kannan, László Lovász, Miklós Simonovits:
Isoperimetric Problems for Convex Bodies and a Localization Lemama. Discret. Comput. Geom. 13: 541-559 (1995) - [j24]Ravi Kannan, John Mount, Sridhar R. Tayur:
A Randomized Algorithm to Optimize Over Certain Convex Sets. Math. Oper. Res. 20(3): 529-549 (1995) - 1994
- [c19]Ravi Kannan:
Markov Chains and Polynomial Time Algorithms. FOCS 1994: 656-671 - 1993
- [j23]Martin E. Dyer, Alan M. Frieze, Ravi Kannan, Ajai Kapoor, Ljubomir Perkovic, Umesh V. Vazirani:
A Mildly Exponential Time Algorithm for Approximating the Number of Solutions to a Multidimensional Knapsack Problem. Comb. Probab. Comput. 2: 271-284 (1993) - [j22]Ravi Kannan, H. Venkateswaran, V. Vinay, Andrew Chi-Chih Yao:
A Circuit-Based Proof of Toda's Theorem. Inf. Comput. 104(2): 271-276 (1993) - [c18]Avrim Blum, Ravi Kannan:
Learning an Intersection of k Halfspaces over a Uniform Distribution. FOCS 1993: 312-320 - [c17]Ravi Kannan:
Optimal solution and value of parametric integer programs. IPCO 1993: 11-21 - 1992
- [j21]William J. Cook, Mark Hartmann, Ravi Kannan, Colin McDiarmid:
On integer points in polyhedra. Comb. 12(1): 27-37 (1992) - [j20]Ravi Kannan:
Lattice translates of a polytope and the Frobenius problem. Comb. 12(2): 161-177 (1992) - [e2]Egon Balas, Gérard Cornuéjols, Ravi Kannan:
Proceedings of the 2nd Integer Programming and Combinatorial Optimization Conference, Pittsburgh, PA, USA, May 1992. Carnegie Mellon University 1992 [contents] - 1991
- [j19]Martin E. Dyer, Alan M. Frieze, Ravi Kannan:
A Random Polynomial Time Algorithm for Approximating the Volume of Convex Bodies. J. ACM 38(1): 1-17 (1991) - [c16]David L. Applegate, Ravi Kannan:
Sampling and Integration of Near Log-Concave functions. STOC 1991: 156-163 - 1990
- [j18]Ravi Kannan, László Lovász, Herbert E. Scarf:
The Shapes of Polyhedra. Math. Oper. Res. 15(2): 364-380 (1990) - [j17]William J. Cook, Ravi Kannan, Alexander Schrijver:
Chvátal Closures for mixed Integer Programming Problems. Math. Program. 47: 155-174 (1990) - [c15]Ravi Kannan:
Test Sets for Integer Programs, 0_ Sentences. Polyhedral Combinatorics 1990: 39-48 - [e1]Ravi Kannan, William R. Pulleyblank:
Proceedings of the 1st Integer Programming and Combinatorial Optimization Conference, Waterloo, Ontorio, Canada, May 28-30 1990. University of Waterloo Press 1990, ISBN 0-88898-099-X [contents]
1980 – 1989
- 1989
- [j16]Zvi Galil, Ravi Kannan, Endre Szemerédi:
On 3-pushdown graphs with large separators. Comb. 9(1): 9-19 (1989) - [j15]Zvi Galil, Ravi Kannan, Endre Szemerédi:
On Nontrivial Separators for k-Page Graphs and Simulations by Nondeterministic One-Tape Turing Machines. J. Comput. Syst. Sci. 38(1): 134-149 (1989) - [j14]