Ravi Kannan

According to our database, Ravi Kannan authored at least 125 papers between 1979 and 2024.

Collaborative distances:

• Dijkstra number of two.
• Erdős number of two.

2024

LevAttention: Time, Space, and Streaming Efficient Algorithm for Heavy Attentions.

Ravindran Kannan, Chiranjib Bhattacharyya, Praneeth Kacham, David P. Woodruff

CoRR, 2024

Random Separating Hyperplane Theorem and Learning Polytopes.

Chiranjib Bhattacharyya, Ravindran Kannan, Amit Kumar

Proceedings of the 51st International Colloquium on Automata, Languages, and Programming, 2024

2023

Bit Complexity of Jordan Normal Form and Polynomial Spectral Factorization.

Papri Dey, Ravi Kannan, Nick Ryder, Nikhil Srivastava

Proceedings of the 14th Innovations in Theoretical Computer Science Conference, 2023

2022

How many Clusters? - An algorithmic answer.

Chiranjib Bhattacharyya, Ravindran Kannan, Amit Kumar

Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, 2022

2021

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.

Ravindran Kannan, Narender Singh, Andrzej Przekwas, Xianlian Zhou, Ross Walenga, Andrew Babiskin

J. Comput. Des. Eng., 2021

Bit Complexity of Jordan Normal Form and Spectral Factorization.

Papri Dey, Ravi Kannan, Nick Ryder, Nikhil Srivastava

CoRR, 2021

Finding k in Latent k- polytope.

Chiranjib Bhattacharyya, Ravindran Kannan, Amit Kumar

Proceedings of the 38th International Conference on Machine Learning, 2021

Learning a Latent Simplex in Input Sparsity Time.

Ainesh Bakshi, Chiranjib Bhattacharyya, Ravi Kannan, David P. Woodruff, Samson Zhou

Proceedings of the 9th International Conference on Learning Representations, 2021

2020

Algorithms for finding k in k-means.

Chiranjib Bhattacharyya, Ravindran Kannan, Amit Kumar

CoRR, 2020

Finding a latent <i>k</i>-simplex in <i>O</i>* (<i>k</i> · nnz(data)) time via Subset Smoothing.

Chiranjib Bhattacharyya, Ravindran Kannan

Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020

Near-optimal sample complexity bounds for learning Latent k-polytopes and applications to Ad-Mixtures.

Chiranjib Bhattacharyya, Ravindran Kannan

Proceedings of the 37th International Conference on Machine Learning, 2020

2019

Finding a latent k-simplex in O(k . nnz(data)) time via Subset Smoothing.

Chiranjib Bhattacharyya, Ravindran Kannan

CoRR, 2019

2017

Randomized algorithms in numerical linear algebra.

Ravindran Kannan, Santosh S. Vempala

Acta Numer., 2017

The Hidden Hubs Problem.

Ravindran Kannan, Santosh S. Vempala

Proceedings of the 30th Conference on Learning Theory, 2017

2016

Computing a Nonnegative Matrix Factorization - Provably.

Sanjeev Arora, Rong Ge, Ravi Kannan, Ankur Moitra

SIAM J. Comput., 2016

Recent Advances in Randomized Numerical Linear Algebra (NII Shonan Meeting 2016-10).

Ravindran Kannan, Michael W. Mahoney, David P. Woodruff

NII Shonan Meet. Rep., 2016

Beyond Spectral: Tight Bounds for Planted Gaussians.

Ravi Kannan, Santosh S. Vempala

CoRR, 2016

Non-negative Matrix Factorization under Heavy Noise.

Chiranjib Bhattacharyya, Navin Goyal, Ravindran Kannan, Jagdeep Pani

Proceedings of the 33nd International Conference on Machine Learning, 2016

2015

Markets with Production: A Polynomial Time Algorithm and a Reduction to Pure Exchange.

Jugal Garg, Ravi Kannan

Proceedings of the Sixteenth ACM Conference on Economics and Computation, 2015

2014

14th Knuth prize: call for nominations.

Ravindran Kannan

SIGACT News, 2014

A simple randomised algorithm for convex optimisation - Application to two-stage stochastic programming.

Martin E. Dyer, Ravi Kannan, Leen Stougie

Math. Program., 2014

A provable SVD-based algorithm for learning topics in dominant admixture corpus.

Trapit Bansal, Chiranjib Bhattacharyya, Ravindran Kannan

Proceedings of the Advances in Neural Information Processing Systems 27: Annual Conference on Neural Information Processing Systems 2014, 2014

Spectral Approaches to Nearest Neighbor Search.

Amirali Abdullah, Alexandr Andoni, Ravindran Kannan, Robert Krauthgamer

Proceedings of the 55th IEEE Annual Symposium on Foundations of Computer Science, 2014

Principal Component Analysis and Higher Correlations for Distributed Data.

Ravi Kannan, Santosh S. Vempala, David P. Woodruff

Proceedings of The 27th Conference on Learning Theory, 2014

2013

Nimble Algorithms for Cloud Computing

Ravindran Kannan, Santosh S. Vempala

CoRR, 2013

2012

Random Walks on Polytopes and an Affine Interior Point Method for Linear Programming.

Ravindran Kannan, Hariharan Narayanan

Math. Oper. Res., 2012

Zero-One Rounding of Singular Vectors.

Amit Deshpande, Ravindran Kannan, Nikhil Srivastava

Proceedings of the Automata, Languages, and Programming - 39th International Colloquium, 2012

2011

Algorithms: Recent Highlights and Challenges.

Ravi Kannan

SIGARCH Comput. Archit. News, 2011

2010

Spectral methods for matrices and tensors.

Ravindran Kannan

Proceedings of the 42nd ACM Symposium on Theory of Computing, 2010

Clustering with Spectral Norm and the k-Means Algorithm.

Amit Kumar, Ravindran Kannan

Proceedings of the 51th Annual IEEE Symposium on Foundations of Computer Science, 2010

2009

Pass-Efficient Algorithms for Learning Mixtures of Uniform Distributions.

Kevin L. Chang, Ravi Kannan

SIAM J. Comput., 2009

Optimization of a convex program with a polynomial perturbation.

Ravi Kannan, Luis Rademacher

Oper. Res. Lett., 2009

Spectral Algorithms.

Ravi Kannan, Santosh S. Vempala

Found. Trends Theor. Comput. Sci., 2009

Finding Dense Subgraphs in <i>G</i>(<i>n</i>, 1/2).

Atish Das Sarma, Amit Deshpande, Ravi Kannan

Proceedings of the Approximation and Online Algorithms, 7th International Workshop, 2009

Preface -- IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (2009).

Ravi Kannan, K. Narayan Kumar

Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2009

A New Probability Inequality Using Typical Moments and Concentration Results.

Ravindran Kannan

Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science, 2009

Discovering Global Patterns in Linguistic Networks through Spectral Analysis: A Case Study of the Consonant Inventories.

Animesh Mukherjee, Monojit Choudhury, Ravi Kannan

Proceedings of the EACL 2009, 12th Conference of the European Chapter of the Association for Computational Linguistics, Proceedings of the Conference, Athens, Greece, March 30, 2009

Adaptive Sampling for k-Means Clustering.

Ankit Aggarwal, Amit Deshpande, Ravi Kannan

Proceedings of the Approximation, 2009

2008

The Spectral Method for General Mixture Models.

Ravindran Kannan, Hadi Salmasian, Santosh S. Vempala

SIAM J. Comput., 2008

Sampling subproblems of heterogeneous Max-Cut problems and approximation algorithms.

Petros Drineas, Ravi Kannan, Michael W. Mahoney

Random Struct. Algorithms, 2008

Finding Dense Subgraphs in G(n,1/2)

Atish Das Sarma, Amit Deshpande, Ravi Kannan

CoRR, 2008

A new approach to the planted clique problem.

Alan M. Frieze, Ravi Kannan

Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2008

Market Equilibria in Polynomial Time for Fixed Number of Goods or Agents.

Nikhil R. Devanur, Ravi Kannan

Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, 2008

2007

Games of fixed rank: a hierarchy of bimatrix games.

Ravi Kannan, Thorsten Theobald

Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2007

Spectral clustering with limited independence.

Anirban Dasgupta, John E. Hopcroft, Ravi Kannan, Pradipta Prometheus Mitra

Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2007

2006

A divide-and-merge methodology for clustering.

David Cheng, Ravi Kannan, Santosh S. Vempala, Grant Wang

ACM Trans. Database Syst., 2006

Fast Monte Carlo Algorithms for Matrices III: Computing a Compressed Approximate Matrix Decomposition.

Petros Drineas, Ravi Kannan, Michael W. Mahoney

SIAM J. Comput., 2006

Fast Monte Carlo Algorithms for Matrices II: Computing a Low-Rank Approximation to a Matrix.

Petros Drineas, Ravi Kannan, Michael W. Mahoney

SIAM J. Comput., 2006

Fast Monte Carlo Algorithms for Matrices I: Approximating Matrix Multiplication.

Petros Drineas, Ravi Kannan, Michael W. Mahoney

SIAM J. Comput., 2006

Approximation of Global MAX-CSP Problems.

Wenceslas Fernandez de la Vega, Ravi Kannan, Marek Karpinski

Electron. Colloquium Comput. Complex., 2006

Blocking Conductance and Mixing in Random Walks.

Ravi Kannan, László Lovász, Ravi Montenegro

Comb. Probab. Comput., 2006

The space complexity of pass-efficient algorithms for clustering.

Kevin L. Chang, Ravi Kannan

Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2006

Spectral Clustering by Recursive Partitioning.

Anirban Dasgupta, John E. Hopcroft, Ravi Kannan, Pradipta Prometheus Mitra

Proceedings of the Algorithms, 2006

2005

Tensor decomposition and approximation schemes for constraint satisfaction problems.

Wenceslas Fernandez de la Vega, Marek Karpinski, Ravi Kannan, Santosh S. Vempala

Proceedings of the 37th Annual ACM Symposium on Theory of Computing, 2005

Sampling Sub-problems of Heterogeneous Max-cut Problems and Approximation Algorithms.

Petros Drineas, Ravi Kannan, Michael W. Mahoney

Proceedings of the STACS 2005, 2005

2004

Clustering Large Graphs via the Singular Value Decomposition.

Petros Drineas, Alan M. Frieze, Ravi Kannan, Santosh S. Vempala, V. Vinay

Mach. Learn., 2004

On clusterings: Good, bad and spectral.

Ravi Kannan, Santosh S. Vempala, Adrian Vetta

J. ACM, 2004

Fast monte-carlo algorithms for finding low-rank approximations.

Alan M. Frieze, Ravi Kannan, Santosh S. Vempala

J. ACM, 2004

The Spectral Method for Mixture Models

Hadi Salmasian, Ravindran Kannan, Santosh S. Vempala

Electron. Colloquium Comput. Complex., 2004

2003

Random sampling and approximation of MAX-CSPs.

Noga Alon, Wenceslas Fernandez de la Vega, Ravi Kannan, Marek Karpinski

J. Comput. Syst. Sci., 2003

Pass efficient algorithms for approximating large matrices.

Petros Drineas, Ravi Kannan

Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2003

Rapid Mixing of Several Markov Chains for a Hard-Core Model.

Ravi Kannan, Michael W. Mahoney, Ravi Montenegro

Proceedings of the Algorithms and Computation, 14th International Symposium, 2003

2002

A deterministic (2-2/(k+1))ⁿ algorithm for k-SAT based on local search.

Evgeny Dantsin, Andreas Goerdt, Edward A. Hirsch, Ravi Kannan, Jon M. Kleinberg, Christos H. Papadimitriou, Prabhakar Raghavan, Uwe Schöning

Theor. Comput. Sci., 2002

2001

Random Sampling and Approximation of MAX-CSP Problems

Noga Alon, Wenceslas Fernandez de la Vega, Ravi Kannan, Marek Karpinski

Electron. Colloquium Comput. Complex., 2001

Learning mixtures of arbitrary gaussians.

Sanjeev Arora, Ravi Kannan

Proceedings of the Proceedings on 33rd Annual ACM Symposium on Theory of Computing, 2001

Fast Monte-Carlo Algorithms for Approximate Matrix Multiplication.

Petros Drineas, Ravi Kannan

Proceedings of the 42nd Annual Symposium on Foundations of Computer Science, 2001

1999

Simple Markov-chain algorithms for generating bipartite graphs and tournaments.

Ravi Kannan, Prasad Tetali, Santosh S. Vempala

Random Struct. Algorithms, 1999

A Simple Algorithm for Constructing Szemere'di's Regularity Partition.

Alan M. Frieze, Ravi Kannan

Electron. J. Comb., 1999

Quick Approximation to Matrices and Applications.

Alan M. Frieze, Ravi Kannan

Comb., 1999

Faster Mixing via Average Conductance.

László Lovász, Ravi Kannan

Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, 1999

Clustering in Large Graphs and Matrices.

Petros Drineas, Alan M. Frieze, Ravi Kannan, Santosh S. Vempala, V. Vinay

Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, 1999

1998

A Polynomial-Time Algorithm for Learning Noisy Linear Threshold Functions.

Avrim Blum, Alan M. Frieze, Ravi Kannan, Santosh S. Vempala

Algorithmica, 1998

Local Search in Smooth Convex Sets.

Ravi Kannan, Andreas Nolte

Proceedings of the 39th Annual Symposium on Foundations of Computer Science, 1998

Approximation of Diameters: Randomization Doesn't Help.

Andreas Brieden, Peter Gritzmann, Ravi Kannan, Victor Klee, László Lovász, Miklós Simonovits

Proceedings of the 39th Annual Symposium on Foundations of Computer Science, 1998

A Fast Random Greedy Algorithm for the Component Commonality Problem.

Ravi Kannan, Andreas Nolte

Proceedings of the Algorithms, 1998

1997

Random walks and an O^*(n⁵) volume algorithm for convex bodies.

Ravi Kannan, László Lovász, Miklós Simonovits

Random Struct. Algorithms, 1997

Sampling contingency tables.

Martin E. Dyer, Ravi Kannan, John Mount

Random Struct. Algorithms, 1997

On Barvinok's Algorithm for Counting Lattice Points in Fixed Dimension.

Martin E. Dyer, Ravi Kannan

Math. Oper. Res., 1997

Learning an Intersection of a Constant Number of Halfspaces over a Uniform Distribution.

Avrim Blum, Ravindran Kannan

J. Comput. Syst. Sci., 1997

Sampling Lattice Points.

Ravi Kannan, Santosh S. Vempala

Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing, 1997

Simple Markov-Chain Algorithms for Generating Bipartite Graphs and Tournaments (Extended Abstract).

Ravi Kannan, Prasad Tetali, Santosh S. Vempala

Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 1997

1996

Sampling According to the Multivariate Normal Density.

Ravi Kannan, Guangxing Li

Proceedings of the 37th Annual Symposium on Foundations of Computer Science, 1996

The Regularity Lemma and Approximation Schemes for Dense Problems.

Alan M. Frieze, Ravi Kannan

Proceedings of the 37th Annual Symposium on Foundations of Computer Science, 1996

Learning Linear Transformations.

Alan M. Frieze, Mark Jerrum, Ravi Kannan

Proceedings of the 37th Annual Symposium on Foundations of Computer Science, 1996

1995

A Randomized Algorithm to Optimize Over Certain Convex Sets.

Ravi Kannan, John Mount, Sridhar R. Tayur

Math. Oper. Res., 1995

Isoperimetric Problems for Convex Bodies and a Localization Lemama.

Ravi Kannan, László Lovász, Miklós Simonovits

Discret. Comput. Geom., 1995

1994

Markov Chains and Polynomial Time Algorithms

Ravi Kannan

Proceedings of the 35th Annual Symposium on Foundations of Computer Science, 1994

1993

A Circuit-Based Proof of Toda's Theorem

Ravi Kannan, H. Venkateswaran, V. Vinay, Andrew Chi-Chih Yao

Inf. Comput., June, 1993

A Mildly Exponential Time Algorithm for Approximating the Number of Solutions to a Multidimensional Knapsack Problem.

Martin E. Dyer, Alan M. Frieze, Ravi Kannan, Ajai Kapoor, Ljubomir Perkovic, Umesh V. Vazirani

Comb. Probab. Comput., 1993

Optimal solution and value of parametric integer programs.

Ravi Kannan

Proceedings of the 3rd Integer Programming and Combinatorial Optimization Conference, Erice, Italy, April 29, 1993

Learning an Intersection of k Halfspaces over a Uniform Distribution

Avrim Blum, Ravi Kannan

Proceedings of the 34th Annual Symposium on Foundations of Computer Science, 1993

1992

Lattice translates of a polytope and the Frobenius problem.

Ravi Kannan

Comb., 1992

On integer points in polyhedra.

William J. Cook, Mark Hartmann, Ravi Kannan, Colin McDiarmid

Comb., 1992

1991

A Random Polynomial Time Algorithm for Approximating the Volume of Convex Bodies.

Martin E. Dyer, Alan M. Frieze, Ravi Kannan

J. ACM, 1991

Sampling and Integration of Near Log-Concave functions

David L. Applegate, Ravi Kannan

Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, 1991

1990

Chvátal Closures for mixed Integer Programming Problems.

William J. Cook, Ravi Kannan, Alexander Schrijver

Math. Program., 1990

The Shapes of Polyhedra.

Ravi Kannan, László Lovász, Herbert E. Scarf

Math. Oper. Res., 1990

Test Sets for Integer Programs, 0_ Sentences.

Ravi Kannan

Proceedings of the Polyhedral Combinatorics, 1990

1989

Succinct Certificates for Almost All Subset Sum Problems.

Merrick L. Furst, Ravi Kannan

SIAM J. Comput., 1989

On Nontrivial Separators for k-Page Graphs and Simulations by Nondeterministic One-Tape Turing Machines.

Zvi Galil, Ravi Kannan, Endre Szemerédi

J. Comput. Syst. Sci., 1989

On 3-pushdown graphs with large separators.

Zvi Galil, Ravi Kannan, Endre Szemerédi

Comb., 1989

The Frobenius Problem.

Ravi Kannan

Proceedings of the Foundations of Software Technology and Theoretical Computer Science, 1989

1988

Reconstructing Truncated Integer Variables Satisfying Linear Congruences.

Alan M. Frieze, Johan Håstad, Ravi Kannan, J. C. Lagarias, Adi Shamir

SIAM J. Comput., 1988

1987

Sublinear Parallel Algorithm for Computing the Greatest Common Divisor of Two Integers.

Ravindran Kannan, Gary L. Miller, Larry Rudolph

SIAM J. Comput., 1987

Minkowski's Convex Body Theorem and Integer Programming.

Ravi Kannan

Math. Oper. Res., 1987

Convex Hull of Randomly Chosen Points from A Polytope.

Rex A. Dwyer, Ravi Kannan

Proceedings of the Parallel Algorithms and Architectures, 1987

1986

Polynomial-time algorithm for the orbit problem.

Ravindran Kannan, Richard J. Lipton

J. ACM, 1986

Covering Minima and Lattice Point Free Convex Bodies.

Ravi Kannan, László Lovász

Proceedings of the Foundations of Software Technology and Theoretical Computer Science, 1986

Basis Reduction and Evidence for Transcendence of Certain Numbers.

Ravi Kannan

Proceedings of the Foundations of Software Technology and Theoretical Computer Science, 1986

1985

Solving Systems of Linear Equations over Polynomials.

Ravindran Kannan

Theor. Comput. Sci., 1985

Unraveling k-page graphs

Ravi Kannan

Inf. Control., 1985

1984

Towards Separating Nondeterminism from Determinism.

Ravindran Kannan

Math. Syst. Theory, 1984

Polynomial Factorization and Nonrandomness of Bits of Algebraic and Some Transcendental Numbers

Ravindran Kannan, Arjen K. Lenstra, László Lovász

Proceedings of the 16th Annual ACM Symposium on Theory of Computing, April 30, 1984

Linear Congruential Generators Do Not Produce Random Sequences

Alan M. Frieze, Ravi Kannan, J. C. Lagarias

Proceedings of the 25th Annual Symposium on Foundations of Computer Science, 1984

1983

Polynomial-Time Aggregation of Integer Programming Problems

Ravindran Kannan

J. ACM, January, 1983

Alternation and the Power of Nondeterminism

Ravi Kannan

Proceedings of the 15th Annual ACM Symposium on Theory of Computing, 1983

Improved Algorithms for Integer Programming and Related Lattice Problems

Ravi Kannan

Proceedings of the 15th Annual ACM Symposium on Theory of Computing, 1983

1982

Circuit-Size Lower Bounds and Non-Reducibility to Sparse Sets

Ravi Kannan

Inf. Control., 1982

1981

Exponential Lower Bounds on a Class of Knapsack Algorithms.

Dirk Hausmann, Ravindran Kannan, Bernhard Korte

Math. Oper. Res., 1981

A Circuit-Size Lower Bound

Ravi Kannan

Proceedings of the 22nd Annual Symposium on Foundations of Computer Science, 1981

Towards Separating Nondeterministic Time from Deterministic Time

Ravi Kannan

Proceedings of the 22nd Annual Symposium on Foundations of Computer Science, 1981

1980

A Polynomial Algorithm for the Two-Variable Integer Programming Problem.

Ravindran Kannan

J. ACM, 1980

A characterization of threshold matroids.

Rick Giles, Ravindran Kannan

Discret. Math., 1980

The Orbit Problem is Decidable

Ravindran Kannan, Richard J. Lipton

Proceedings of the 12th Annual ACM Symposium on Theory of Computing, 1980

1979

Polynomial Algorithms for Computing the Smith and Hermite Normal Forms of an Integer Matrix.

Ravindran Kannan, Achim Bachem

SIAM J. Comput., 1979