Ravi Kannan

Publication Activity (10 Years)

Years Active: 1981-2023
Publications (10 Years): 7

Top Venues

CoRR

ITCS

ICLR

Publications

Papri Dey, Ravi Kannan, Nick Ryder, Nikhil Srivastava
Bit Complexity of Jordan Normal Form and Polynomial Spectral Factorization. ITCS (2023)
Ainesh Bakshi, Chiranjib Bhattacharyya, Ravi Kannan, David P. Woodruff, Samson Zhou
Learning a Latent Simplex in Input-Sparsity Time. CoRR (2021)
Ainesh Bakshi, Chiranjib Bhattacharyya, Ravi Kannan, David P. Woodruff, Samson Zhou
Learning a Latent Simplex in Input Sparsity Time. ICLR (2021)
Papri Dey, Ravi Kannan, Nick Ryder, Nikhil Srivastava
Bit Complexity of Jordan Normal Form and Spectral Factorization. CoRR (2021)
Ravi Kannan, Santosh S. Vempala
Beyond Spectral: Tight Bounds for Planted Gaussians. CoRR (2016)
Sanjeev Arora, Rong Ge, Ravi Kannan, Ankur Moitra
Computing a Nonnegative Matrix Factorization - Provably. SIAM J. Comput. 45 (4) (2016)
Jugal Garg, Ravi Kannan
Markets with Production: A Polynomial Time Algorithm and a Reduction to Pure Exchange. EC (2015)
Ravi Kannan, Santosh S. Vempala, David P. Woodruff
Principal Component Analysis and Higher Correlations for Distributed Data. COLT (2014)
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) (2014)
Sanjeev Arora, Rong Ge, Ravi Kannan, Ankur Moitra
Computing a Nonnegative Matrix Factorization -- Provably CoRR (2011)
Ravi Kannan
Algorithms: Recent Highlights and Challenges. SIGARCH Comput. Archit. News 39 (3) (2011)
Kevin L. Chang, Ravi Kannan
Pass-Efficient Algorithms for Learning Mixtures of Uniform Distributions. SIAM J. Comput. 39 (3) (2009)
Ravi Kannan, Luis Rademacher
Optimization of a convex program with a polynomial perturbation. Oper. Res. Lett. 37 (6) (2009)
Animesh Mukherjee, Monojit Choudhury, Ravi Kannan
Discovering Global Patterns in Linguistic Networks through Spectral Analysis: A Case Study of the Consonant Inventories. EACL (2009)
Ravi Kannan, Santosh S. Vempala
Spectral Algorithms. Found. Trends Theor. Comput. Sci. 4 (3-4) (2009)
Ravi Kannan, Hariharan Narayanan
Random walks on polytopes and an affine interior point method for linear programming. STOC (2009)
Ankit Aggarwal, Amit Deshpande, Ravi Kannan
Adaptive Sampling for k-Means Clustering. APPROX-RANDOM (2009)
Animesh Mukherjee, Monojit Choudhury, Ravi Kannan
Discovering Global Patterns in Linguistic Networks through Spectral Analysis: A Case Study of the Consonant Inventories CoRR (2009)
Ravi Kannan, K. Narayan Kumar
Preface -- IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (2009). FSTTCS (2009)
Atish Das Sarma, Amit Deshpande, Ravi Kannan
, 1/2). WAOA (2009)
Alan M. Frieze, Ravi Kannan
A new approach to the planted clique problem. FSTTCS (2008)
Nikhil R. Devanur, Ravi Kannan
Market Equilibria in Polynomial Time for Fixed Number of Goods or Agents. FOCS (2008)
Petros Drineas, Ravi Kannan, Michael W. Mahoney
Sampling subproblems of heterogeneous Max-Cut problems and approximation algorithms. Random Struct. Algorithms 32 (3) (2008)
Atish Das Sarma, Amit Deshpande, Ravi Kannan
Finding Dense Subgraphs in G(n,1/2) CoRR (2008)
Ravi Kannan, Thorsten Theobald
Games of fixed rank: a hierarchy of bimatrix games. SODA (2007)
Anirban Dasgupta, John E. Hopcroft, Ravi Kannan, Pradipta Prometheus Mitra
Spectral clustering with limited independence. SODA (2007)
Anirban Dasgupta, John E. Hopcroft, Ravi Kannan, Pradipta Prometheus Mitra
Spectral Clustering by Recursive Partitioning. ESA (2006)
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) (2006)
Wenceslas Fernandez de la Vega, Ravi Kannan, Marek Karpinski
Approximation of Global MAX-CSP Problems. Electron. Colloquium Comput. Complex. 13 (124) (2006)
Ravi Kannan, László Lovász, Ravi Montenegro
Blocking Conductance and Mixing in Random Walks. Comb. Probab. Comput. 15 (4) (2006)
Petros Drineas, Ravi Kannan, Michael W. Mahoney
Fast Monte Carlo Algorithms for Matrices I: Approximating Matrix Multiplication. SIAM J. Comput. 36 (1) (2006)
David Cheng, Ravi Kannan, Santosh S. Vempala, Grant Wang
A divide-and-merge methodology for clustering. ACM Trans. Database Syst. 31 (4) (2006)
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) (2006)
Kevin L. Chang, Ravi Kannan
The space complexity of pass-efficient algorithms for clustering. SODA (2006)
Wenceslas Fernandez de la Vega, Marek Karpinski, Ravi Kannan, Santosh S. Vempala
Tensor decomposition and approximation schemes for constraint satisfaction problems. STOC (2005)
Petros Drineas, Ravi Kannan, Michael W. Mahoney
Sampling Sub-problems of Heterogeneous Max-cut Problems and Approximation Algorithms. STACS (2005)
David Cheng, Santosh S. Vempala, Ravi Kannan, Grant Wang
A divide-and-merge methodology for clustering. PODS (2005)
Ravi Kannan, Thorsten Theobald
Games of fixed rank: A hierarchy of bimatrix games CoRR (2005)
Ravi Kannan, Santosh S. Vempala, Adrian Vetta
On clusterings: Good, bad and spectral. J. ACM 51 (3) (2004)
Alan M. Frieze, Ravi Kannan, Santosh S. Vempala
Fast monte-carlo algorithms for finding low-rank approximations. J. ACM 51 (6) (2004)
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) (2004)
Petros Drineas, Ravi Kannan
Pass efficient algorithms for approximating large matrices. SODA (2003)
Ravi Kannan, Michael W. Mahoney, Ravi Montenegro
Rapid Mixing of Several Markov Chains for a Hard-Core Model. ISAAC (2003)
Noga Alon, Wenceslas Fernandez de la Vega, Ravi Kannan, Marek Karpinski
Random sampling and approximation of MAX-CSPs. J. Comput. Syst. Sci. 67 (2) (2003)
Evgeny Dantsin, Andreas Goerdt, Edward A. Hirsch, Ravi Kannan, Jon M. Kleinberg, Christos H. Papadimitriou, Prabhakar Raghavan, Uwe Schöning
algorithm for k-SAT based on local search. Theor. Comput. Sci. 289 (1) (2002)
Noga Alon, Wenceslas Fernandez de la Vega, Ravi Kannan, Marek Karpinski
Random sampling and approximation of MAX-CSP problems. STOC (2002)
Petros Drineas, Ravi Kannan
Fast Monte-Carlo Algorithms for Approximate Matrix Multiplication. FOCS (2001)
Noga Alon, Wenceslas Fernandez de la Vega, Ravi Kannan, Marek Karpinski
Random Sampling and Approximation of MAX-CSP Problems Electron. Colloquium Comput. Complex. (100) (2001)
Sanjeev Arora, Ravi Kannan
Learning mixtures of arbitrary gaussians. STOC (2001)
Ravi Kannan, Santosh S. Vempala, Adrian Vetta
On Clusterings - Good, Bad and Spectral. FOCS (2000)
Ravi Kannan, Prasad Tetali, Santosh S. Vempala
Simple Markov-chain algorithms for generating bipartite graphs and tournaments. Random Struct. Algorithms 14 (4) (1999)
Alan M. Frieze, Ravi Kannan
A Simple Algorithm for Constructing Szemere'di's Regularity Partition. Electron. J. Comb. 6 (1999)
Alan M. Frieze, Ravi Kannan
Quick Approximation to Matrices and Applications. Comb. 19 (2) (1999)
Petros Drineas, Alan M. Frieze, Ravi Kannan, Santosh S. Vempala, V. Vinay
Clustering in Large Graphs and Matrices. SODA (1999)
László Lovász, Ravi Kannan
Faster Mixing via Average Conductance. STOC (1999)
Avrim Blum, Alan M. Frieze, Ravi Kannan, Santosh S. Vempala
A Polynomial-Time Algorithm for Learning Noisy Linear Threshold Functions. Algorithmica 22 (1/2) (1998)
Ravi Kannan, Andreas Nolte
Local Search in Smooth Convex Sets. FOCS (1998)
Alan M. Frieze, Ravi Kannan, Santosh S. Vempala
Fast Monte-Carlo Algorithms for Finding Low-Rank Approximations. FOCS (1998)
Ravi Kannan, Andreas Nolte
A Fast Random Greedy Algorithm for the Component Commonality Problem. ESA (1998)
Andreas Brieden, Peter Gritzmann, Ravi Kannan, Victor Klee, László Lovász, Miklós Simonovits
Approximation of Diameters: Randomization Doesn't Help. FOCS (1998)
Martin E. Dyer, Ravi Kannan, John Mount
Sampling contingency tables. Random Struct. Algorithms 10 (4) (1997)
Ravi Kannan, Santosh S. Vempala
Sampling Lattice Points. STOC (1997)
Martin E. Dyer, Ravi Kannan
On Barvinok's Algorithm for Counting Lattice Points in Fixed Dimension. Math. Oper. Res. 22 (3) (1997)
Ravi Kannan, Prasad Tetali, Santosh S. Vempala
Simple Markov-Chain Algorithms for Generating Bipartite Graphs and Tournaments (Extended Abstract). SODA (1997)
Ravi Kannan, László Lovász, Miklós Simonovits
) volume algorithm for convex bodies. Random Struct. Algorithms 11 (1) (1997)
Ravi Kannan, Guangxing Li
Sampling According to the Multivariate Normal Density. FOCS (1996)
Alan M. Frieze, Ravi Kannan
The Regularity Lemma and Approximation Schemes for Dense Problems. FOCS (1996)
Alan M. Frieze, Mark Jerrum, Ravi Kannan
Learning Linear Transformations. FOCS (1996)
Avrim Blum, Alan M. Frieze, Ravi Kannan, Santosh S. Vempala
A Polynomial-Time Algorithm for Learning Noisy Linear Threshold Functions. FOCS (1996)
Ravi Kannan, John Mount, Sridhar R. Tayur
A Randomized Algorithm to Optimize Over Certain Convex Sets. Math. Oper. Res. 20 (3) (1995)
Ravi Kannan, László Lovász, Miklós Simonovits
Isoperimetric Problems for Convex Bodies and a Localization Lemama. Discret. Comput. Geom. 13 (1995)
Ravi Kannan
Markov Chains and Polynomial Time Algorithms FOCS (1994)
Avrim Blum, Ravi Kannan
Learning an Intersection of k Halfspaces over a Uniform Distribution FOCS (1993)
Ravi Kannan, H. Venkateswaran, V. Vinay, Andrew Chi-Chih Yao
A Circuit-Based Proof of Toda's Theorem Inf. Comput. 104 (2) (1993)
Ravi Kannan
Optimal solution and value of parametric integer programs. IPCO (1993)
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 (1993)
William J. Cook, Mark Hartmann, Ravi Kannan, Colin McDiarmid
On integer points in polyhedra. Comb. 12 (1) (1992)
Ravi Kannan
Lattice translates of a polytope and the Frobenius problem. Comb. 12 (2) (1992)
Martin E. Dyer, Alan M. Frieze, Ravi Kannan
A Random Polynomial Time Algorithm for Approximating the Volume of Convex Bodies. J. ACM 38 (1) (1991)
David L. Applegate, Ravi Kannan
Sampling and Integration of Near Log-Concave functions STOC (1991)
William J. Cook, Ravi Kannan, Alexander Schrijver
Chvátal Closures for mixed Integer Programming Problems. Math. Program. 47 (1990)
Ravi Kannan
Test Sets for Integer Programs, 0_ Sentences. Polyhedral Combinatorics (1990)
Ravi Kannan, László Lovász, Herbert E. Scarf
The Shapes of Polyhedra. Math. Oper. Res. 15 (2) (1990)
Merrick L. Furst, Ravi Kannan
Succinct Certificates for Almost All Subset Sum Problems. SIAM J. Comput. 18 (3) (1989)
Ravi Kannan
The Frobenius Problem. FSTTCS (1989)
Zvi Galil, Ravi Kannan, Endre Szemerédi
On 3-pushdown graphs with large separators. Comb. 9 (1) (1989)
Martin E. Dyer, Alan M. Frieze, Ravi Kannan
A Random Polynomial Time Algorithm for Approximating the Volume of Convex Bodies STOC (1989)
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) (1989)
Alan M. Frieze, Johan Håstad, Ravi Kannan, J. C. Lagarias, Adi Shamir
Reconstructing Truncated Integer Variables Satisfying Linear Congruences. SIAM J. Comput. 17 (2) (1988)
Ravi Kannan
Minkowski's Convex Body Theorem and Integer Programming. Math. Oper. Res. 12 (3) (1987)
Rex A. Dwyer, Ravi Kannan
Convex Hull of Randomly Chosen Points from A Polytope. Parallel Algorithms and Architectures (1987)
Ravi Kannan
Basis Reduction and Evidence for Transcendence of Certain Numbers. FSTTCS (1986)
Ravi Kannan, László Lovász
Covering Minima and Lattice Point Free Convex Bodies. FSTTCS (1986)
Zvi Galil, Ravi Kannan, Endre Szemerédi
On Nontrivial Separators for k-Page Graphs and Simulations by Nondeterministic One-Tape Turing Machines STOC (1986)
Ravi Kannan
Unraveling k-page graphs Inf. Control. 66 (1/2) (1985)
Alan M. Frieze, Ravi Kannan, J. C. Lagarias
Linear Congruential Generators Do Not Produce Random Sequences FOCS (1984)
Ravi Kannan
Alternation and the Power of Nondeterminism STOC (1983)
Ravi Kannan
Improved Algorithms for Integer Programming and Related Lattice Problems STOC (1983)
Ravi Kannan
Circuit-Size Lower Bounds and Non-Reducibility to Sparse Sets Inf. Control. 55 (1-3) (1982)
Ravi Kannan
Towards Separating Nondeterministic Time from Deterministic Time FOCS (1981)

Ravi Kannan.css-eqlu8i{font-size:small;padding-left:4px;}

Publication Activity (10 Years)

Top Topics

Top Venues

Ravi Kannan