Ravi Kannan

According to our database1, Ravi Kannan authored at least 116 papers between 1979 and 2017.

Collaborative distances:
  • Dijkstra number2 of three.
  • Erdős number3 of two.

Awards

ACM Fellow

ACM Fellow 2016, "For contributions to the field of theoretical computer science".

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

Homepages:

On csauthors.net:

Bibliography

2017
The Hidden Hubs Problem.
Proceedings of the 30th Conference on Learning Theory, 2017

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

Non-negative Matrix Factorization under Heavy Noise.
Proceedings of the 33nd International Conference on Machine Learning, 2016

2015
Markets with Production: A Polynomial Time Algorithm and a Reduction to Pure Exchange.
Proceedings of the Sixteenth ACM Conference on Economics and Computation, 2015

2014
14th Knuth prize: call for nominations.
SIGACT News, 2014

A simple randomised algorithm for convex optimisation - Application to two-stage stochastic programming.
Math. Program., 2014

A provable SVD-based algorithm for learning topics in dominant admixture corpus.
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.
Proceedings of the 55th IEEE Annual Symposium on Foundations of Computer Science, 2014

Principal Component Analysis and Higher Correlations for Distributed Data.
Proceedings of The 27th Conference on Learning Theory, 2014

2012
Computing a nonnegative matrix factorization - provably.
Proceedings of the 44th Symposium on Theory of Computing Conference, 2012

Zero-One Rounding of Singular Vectors.
Proceedings of the Automata, Languages, and Programming - 39th International Colloquium, 2012

2011
Algorithms: Recent Highlights and Challenges.
SIGARCH Computer Architecture News, 2011

2010
Spectral methods for matrices and tensors.
Proceedings of the 42nd ACM Symposium on Theory of Computing, 2010

Clustering with Spectral Norm and the k-Means Algorithm.
Proceedings of the 51th Annual IEEE Symposium on Foundations of Computer Science, 2010

2009
Pass-Efficient Algorithms for Learning Mixtures of Uniform Distributions.
SIAM J. Comput., 2009

Optimization of a convex program with a polynomial perturbation.
Oper. Res. Lett., 2009

Spectral Algorithms.
Foundations and Trends in Theoretical Computer Science, 2009

Finding Dense Subgraphs in G(n, 1/2).
Proceedings of the Approximation and Online Algorithms, 7th International Workshop, 2009

Random walks on polytopes and an affine interior point method for linear programming.
Proceedings of the 41st Annual ACM Symposium on Theory of Computing, 2009

Preface -- IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (2009).
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.
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.
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.
Proceedings of the Approximation, 2009

2008
The Spectral Method for General Mixture Models.
SIAM J. Comput., 2008

Sampling subproblems of heterogeneous Max-Cut problems and approximation algorithms.
Random Struct. Algorithms, 2008

A new approach to the planted clique problem.
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.
Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, 2008

2007
Games of fixed rank: a hierarchy of bimatrix games.
Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2007

Spectral clustering with limited independence.
Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2007

2006
A divide-and-merge methodology for clustering.
ACM Trans. Database Syst., 2006

Fast Monte Carlo Algorithms for Matrices III: Computing a Compressed Approximate Matrix Decomposition.
SIAM J. Comput., 2006

Fast Monte Carlo Algorithms for Matrices II: Computing a Low-Rank Approximation to a Matrix.
SIAM J. Comput., 2006

Fast Monte Carlo Algorithms for Matrices I: Approximating Matrix Multiplication.
SIAM J. Comput., 2006

Approximation of Global MAX-CSP Problems.
Electronic Colloquium on Computational Complexity (ECCC), 2006

Blocking Conductance and Mixing in Random Walks.
Combinatorics, Probability & Computing, 2006

The space complexity of pass-efficient algorithms for clustering.
Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2006

Spectral Clustering by Recursive Partitioning.
Proceedings of the Algorithms, 2006

2005
Tensor decomposition and approximation schemes for constraint satisfaction problems.
Proceedings of the 37th Annual ACM Symposium on Theory of Computing, 2005

Sampling Sub-problems of Heterogeneous Max-cut Problems and Approximation Algorithms.
Proceedings of the STACS 2005, 2005

A divide-and-merge methodology for clustering.
Proceedings of the Twenty-fourth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 2005

The Spectral Method for General Mixture Models.
Proceedings of the Learning Theory, 18th Annual Conference on Learning Theory, 2005

2004
Clustering Large Graphs via the Singular Value Decomposition.
Machine Learning, 2004

On clusterings: Good, bad and spectral.
J. ACM, 2004

The Spectral Method for Mixture Models
Electronic Colloquium on Computational Complexity (ECCC), 2004

2003
Random sampling and approximation of MAX-CSPs.
J. Comput. Syst. Sci., 2003

Pass efficient algorithms for approximating large matrices.
Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2003

Rapid Mixing of Several Markov Chains for a Hard-Core Model.
Proceedings of the Algorithms and Computation, 14th International Symposium, 2003

2002
A deterministic (2-2/(k+1))n algorithm for k-SAT based on local search.
Theor. Comput. Sci., 2002

Random sampling and approximation of MAX-CSP problems.
Proceedings of the Proceedings on 34th Annual ACM Symposium on Theory of Computing, 2002

2001
Random Sampling and Approximation of MAX-CSP Problems
Electronic Colloquium on Computational Complexity (ECCC), 2001

Learning mixtures of arbitrary gaussians.
Proceedings of the Proceedings on 33rd Annual ACM Symposium on Theory of Computing, 2001

Fast Monte-Carlo Algorithms for Approximate Matrix Multiplication.
Proceedings of the 42nd Annual Symposium on Foundations of Computer Science, 2001

2000
On Clusterings - Good, Bad and Spectral.
Proceedings of the 41st Annual Symposium on Foundations of Computer Science, 2000

1999
Simple Markov-chain algorithms for generating bipartite graphs and tournaments.
Random Struct. Algorithms, 1999

A Simple Algorithm for Constructing Szemere'di's Regularity Partition.
Electr. J. Comb., 1999

Quick Approximation to Matrices and Applications.
Combinatorica, 1999

Faster Mixing via Average Conductance.
Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, 1999

Clustering in Large Graphs and Matrices.
Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, 1999

1998
Local Search in Smooth Convex Sets.
Proceedings of the 39th Annual Symposium on Foundations of Computer Science, 1998

Fast Monte-Carlo Algorithms for Finding Low-Rank Approximations.
Proceedings of the 39th Annual Symposium on Foundations of Computer Science, 1998

Approximation of Diameters: Randomization Doesn't Help.
Proceedings of the 39th Annual Symposium on Foundations of Computer Science, 1998

A Fast Random Greedy Algorithm for the Component Commonality Problem.
Proceedings of the Algorithms, 1998

1997
Random walks and an O*(n5) volume algorithm for convex bodies.
Random Struct. Algorithms, 1997

Sampling contingency tables.
Random Struct. Algorithms, 1997

On Barvinok's Algorithm for Counting Lattice Points in Fixed Dimension.
Math. Oper. Res., 1997

Learning an Intersection of a Constant Number of Halfspaces over a Uniform Distribution.
J. Comput. Syst. Sci., 1997

Sampling Lattice Points.
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).
Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 1997

1996
Sampling According to the Multivariate Normal Density.
Proceedings of the 37th Annual Symposium on Foundations of Computer Science, 1996

The Regularity Lemma and Approximation Schemes for Dense Problems.
Proceedings of the 37th Annual Symposium on Foundations of Computer Science, 1996

Learning Linear Transformations.
Proceedings of the 37th Annual Symposium on Foundations of Computer Science, 1996

A Polynomial-Time Algorithm for Learning Noisy Linear Threshold Functions.
Proceedings of the 37th Annual Symposium on Foundations of Computer Science, 1996

1995
A Randomized Algorithm to Optimize Over Certain Convex Sets.
Math. Oper. Res., 1995

Isoperimetric Problems for Convex Bodies and a Localization Lemama.
Discrete & Computational Geometry, 1995

1994
Markov Chains and Polynomial Time Algorithms
Proceedings of the 35th Annual Symposium on Foundations of Computer Science, 1994

1993
A Circuit-Based Proof of Toda's Theorem
Inf. Comput., June, 1993

A Mildly Exponential Time Algorithm for Approximating the Number of Solutions to a Multidimensional Knapsack Problem.
Combinatorics, Probability & Computing, 1993

Optimal solution and value of parametric integer programs.
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
Proceedings of the 34th Annual Symposium on Foundations of Computer Science, 1993

1992
Lattice translates of a polytope and the Frobenius problem.
Combinatorica, 1992

On integer points in polyhedra.
Combinatorica, 1992

1991
A Random Polynomial Time Algorithm for Approximating the Volume of Convex Bodies.
J. ACM, 1991

Sampling and Integration of Near Log-Concave functions
Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, 1991

1990
Chvátal Closures for mixed Integer Programming Problems.
Math. Program., 1990

The Shapes of Polyhedra.
Math. Oper. Res., 1990

Test Sets for Integer Programs, 0_ Sentences.
Proceedings of the Polyhedral Combinatorics, 1990

1989
Succinct Certificates for Almost All Subset Sum Problems.
SIAM J. Comput., 1989

On Nontrivial Separators for k-Page Graphs and Simulations by Nondeterministic One-Tape Turing Machines.
J. Comput. Syst. Sci., 1989

On 3-pushdown graphs with large separators.
Combinatorica, 1989

A Random Polynomial Time Algorithm for Approximating the Volume of Convex Bodies
Proceedings of the 21st Annual ACM Symposium on Theory of Computing, 1989

The Frobenius Problem.
Proceedings of the Foundations of Software Technology and Theoretical Computer Science, 1989

1988
Reconstructing Truncated Integer Variables Satisfying Linear Congruences.
SIAM J. Comput., 1988

1987
Sublinear Parallel Algorithm for Computing the Greatest Common Divisor of Two Integers.
SIAM J. Comput., 1987

Minkowski's Convex Body Theorem and Integer Programming.
Math. Oper. Res., 1987

Convex Hull of Randomly Chosen Points from A Polytope.
Proceedings of the Parallel Algorithms and Architectures, 1987

1986
Polynomial-time algorithm for the orbit problem.
J. ACM, 1986

On Nontrivial Separators for k-Page Graphs and Simulations by Nondeterministic One-Tape Turing Machines
Proceedings of the 18th Annual ACM Symposium on Theory of Computing, 1986

Covering Minima and Lattice Point Free Convex Bodies.
Proceedings of the Foundations of Software Technology and Theoretical Computer Science, 1986

Basis Reduction and Evidence for Transcendence of Certain Numbers.
Proceedings of the Foundations of Software Technology and Theoretical Computer Science, 1986

1985
Solving Systems of Linear Equations over Polynomials.
Theor. Comput. Sci., 1985

Unraveling k-page graphs
Information and Control, 1985

1984
Towards Separating Nondeterminism from Determinism.
Mathematical Systems Theory, 1984

Polynomial Factorization and Nonrandomness of Bits of Algebraic and Some Transcendental Numbers
Proceedings of the 16th Annual ACM Symposium on Theory of Computing, April 30, 1984

Sublinear Parallel Algorithm for Computing the Greatest Common Divisor of Two Integers
Proceedings of the 25th Annual Symposium on Foundations of Computer Science, 1984

Linear Congruential Generators Do Not Produce Random Sequences
Proceedings of the 25th Annual Symposium on Foundations of Computer Science, 1984

1983
Polynomial-Time Aggregation of Integer Programming Problems
J. ACM, January, 1983

Alternation and the Power of Nondeterminism
Proceedings of the 15th Annual ACM Symposium on Theory of Computing, 1983

Improved Algorithms for Integer Programming and Related Lattice Problems
Proceedings of the 15th Annual ACM Symposium on Theory of Computing, 1983

1982
Circuit-Size Lower Bounds and Non-Reducibility to Sparse Sets
Information and Control, 1982

1981
Exponential Lower Bounds on a Class of Knapsack Algorithms.
Math. Oper. Res., 1981

A Circuit-Size Lower Bound
Proceedings of the 22nd Annual Symposium on Foundations of Computer Science, 1981

Towards Separating Nondeterministic Time from Deterministic Time
Proceedings of the 22nd Annual Symposium on Foundations of Computer Science, 1981

1980
A Polynomial Algorithm for the Two-Variable Integer Programming Problem.
J. ACM, 1980

A characterization of threshold matroids.
Discrete Mathematics, 1980

The Orbit Problem is Decidable
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.
SIAM J. Comput., 1979


  Loading...