dblp.uni-trier.dewww.uni-trier.de

Ravi Kannan Vis

Ravindran Kannan

List of publications from the DBLP Bibliography Server - FAQ
Coauthor Index - Ask others: ACM DL/Guide - CiteSeerX - CSB - MetaPress - Google - Bing - Yahoo
Home Page

*2009
93EEAnkit Aggarwal, Amit Deshpande, Ravi Kannan: Adaptive Sampling for k-Means Clustering. APPROX-RANDOM 2009: 15-28
92EEAnimesh 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
91EERavi Kannan, Hariharan Narayanan: Random walks on polytopes and an affine interior point method for linear programming. STOC 2009: 561-570
90EEAnimesh 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)
89EERavi Kannan, Santosh Vempala: Spectral Algorithms. Foundations and Trends in Theoretical Computer Science 4(3-4): 157-288 (2009)
2008
88EENikhil R. Devanur, Ravi Kannan: Market Equilibria in Polynomial Time for Fixed Number of Goods or Agents. FOCS 2008: 45-53
87EEAlan M. Frieze, Ravi Kannan: A new approach to the planted clique problem. FSTTCS 2008
86EEA. Das Sarma, Amit Deshpande, Ravi Kannan: Finding Dense Subgraphs in G(n,1/2) CoRR abs/0807.5111: (2008)
85EEPetros Drineas, Ravi Kannan, Michael W. Mahoney: Sampling subproblems of heterogeneous Max-Cut problems and approximation algorithms. Random Struct. Algorithms 32(3): 307-333 (2008)
84EERavindran Kannan, Hadi Salmasian, Santosh Vempala: The Spectral Method for General Mixture Models. SIAM J. Comput. 38(3): 1141-1156 (2008)
2007
83EEAnirban Dasgupta, John E. Hopcroft, Ravi Kannan, Pradipta Prometheus Mitra: Spectral clustering with limited independence. SODA 2007: 1036-1045
82EERavi Kannan, Thorsten Theobald: Games of fixed rank: a hierarchy of bimatrix games. SODA 2007: 1124-1132
2006
81EEAnirban Dasgupta, John E. Hopcroft, Ravi Kannan, Pradipta Prometheus Mitra: Spectral Clustering by Recursive Partitioning. ESA 2006: 256-267
80EEKevin L. Chang, Ravi Kannan: The space complexity of pass-efficient algorithms for clustering. SODA 2006: 1157-1166
79EEDavid Cheng, Ravi Kannan, Santosh Vempala, Grant Wang: A divide-and-merge methodology for clustering. ACM Trans. Database Syst. 31(4): 1499-1525 (2006)
78EERavi Kannan, László Lovász, Ravi Montenegro: Blocking Conductance and Mixing in Random Walks. Combinatorics, Probability & Computing 15(4): 541-570 (2006)
77EEWenceslas Fernandez de la Vega, Ravi Kannan, Marek Karpinski: Approximation of Global MAX-CSP Problems. Electronic Colloquium on Computational Complexity (ECCC) 13(124): (2006)
76EEPetros Drineas, Ravi Kannan, Michael W. Mahoney: Fast Monte Carlo Algorithms for Matrices I: Approximating Matrix Multiplication. SIAM J. Comput. 36(1): 132-157 (2006)
75EEPetros 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)
74EEPetros 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)
2005
73EERavindran Kannan, Hadi Salmasian, Santosh Vempala: The Spectral Method for General Mixture Models. COLT 2005: 444-457
72EEDavid Cheng, Santosh Vempala, Ravi Kannan, Grant Wang: A divide-and-merge methodology for clustering. PODS 2005: 196-205
71EEPetros Drineas, Ravi Kannan, Michael W. Mahoney: Sampling Sub-problems of Heterogeneous Max-cut Problems and Approximation Algorithms. STACS 2005: 57-68
70EEWenceslas Fernandez de la Vega, Marek Karpinski, Ravi Kannan, Santosh Vempala: Tensor decomposition and approximation schemes for constraint satisfaction problems. STOC 2005: 747-754
69EERavi Kannan, Thorsten Theobald: Games of fixed rank: A hierarchy of bimatrix games CoRR abs/cs/0511021: (2005)
2004
68EEHadi Salmasian, Ravindran Kannan, Santosh Vempala: The Spectral Method for Mixture Models Electronic Colloquium on Computational Complexity (ECCC)(067): (2004)
67EERavi Kannan, Santosh Vempala, Adrian Vetta: On clusterings: Good, bad and spectral. J. ACM 51(3): 497-515 (2004)
66EEAlan M. Frieze, Ravi Kannan, Santosh Vempala: Fast monte-carlo algorithms for finding low-rank approximations. J. ACM 51(6): 1025-1041 (2004)
65EEPetros Drineas, Alan M. Frieze, Ravi Kannan, Santosh Vempala, V. Vinay: Clustering Large Graphs via the Singular Value Decomposition. Machine Learning 56(1-3): 9-33 (2004)
2003
64EERavi Kannan, Michael W. Mahoney, Ravi Montenegro: Rapid Mixing of Several Markov Chains for a Hard-Core Model. ISAAC 2003: 663-675
63EEPetros Drineas, Ravi Kannan: Pass efficient algorithms for approximating large matrices. SODA 2003: 223-232
62EENoga 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)
2002
61EENoga Alon, Wenceslas Fernandez de la Vega, Ravi Kannan, Marek Karpinski: Random sampling and approximation of MAX-CSP problems. STOC 2002: 232-239
60 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)
2001
59 Petros Drineas, Ravi Kannan: Fast Monte-Carlo Algorithms for Approximate Matrix Multiplication. FOCS 2001: 452-459
58EESanjeev Arora, Ravi Kannan: Learning mixtures of arbitrary gaussians. STOC 2001: 247-257
57EENoga Alon, Wenceslas Fernandez de la Vega, Ravi Kannan, Marek Karpinski: Random Sampling and Approximation of MAX-CSP Problems Electronic Colloquium on Computational Complexity (ECCC)(100): (2001)
2000
56 Ravi Kannan, Santosh Vempala, Adrian Vetta: On Clusterings - Good, Bad and Spectral. FOCS 2000: 367-377
1999
55EEPetros Drineas, Alan M. Frieze, Ravi Kannan, Santosh Vempala, V. Vinay: Clustering in Large Graphs and Matrices. SODA 1999: 291-299
54EELászló Lovász, Ravi Kannan: Faster Mixing via Average Conductance. STOC 1999: 282-287
53EEAlan M. Frieze, Ravi Kannan: Quick Approximation to Matrices and Applications. Combinatorica 19(2): 175-220 (1999)
52EEAlan M. Frieze, Ravi Kannan: A Simple Algorithm for Constructing Szemere'di's Regularity Partition. Electr. J. Comb. 6: (1999)
51 Ravi Kannan, Prasad Tetali, Santosh Vempala: Simple Markov-chain algorithms for generating bipartite graphs and tournaments. Random Struct. Algorithms 14(4): 293-308 (1999)
1998
50EERavi Kannan, Andreas Nolte: A Fast Random Greedy Algorithm for the Component Commonality Problem. ESA 1998: 223-234
49EERavi Kannan, Andreas Nolte: Local Search in Smooth Convex Sets. FOCS 1998: 218-226
48EEAndreas 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
47EEAlan M. Frieze, Ravi Kannan, Santosh Vempala: Fast Monte-Carlo Algorithms for Finding Low-Rank Approximations. FOCS 1998: 370-378
46 Avrim Blum, Alan M. Frieze, Ravi Kannan, Santosh Vempala: A Polynomial-Time Algorithm for Learning Noisy Linear Threshold Functions. Algorithmica 22(1/2): 35-52 (1998)
1997
45 Ravi Kannan, Prasad Tetali, Santosh Vempala: Simple Markov-Chain Algorithms for Generating Bipartite Graphs and Tournaments (Extended Abstract). SODA 1997: 193-200
44EERavi Kannan, Santosh Vempala: Sampling Lattice Points. STOC 1997: 696-700
43 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)
42 Martin E. Dyer, Ravi Kannan, John Mount: Sampling contingency tables. Random Struct. Algorithms 10(4): 487-506 (1997)
41 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)
1996
40 Alan M. Frieze, Ravi Kannan: The Regularity Lemma and Approximation Schemes for Dense Problems. FOCS 1996: 12-20
39 Ravi Kannan, Guangxing Li: Sampling According to the Multivariate Normal Density. FOCS 1996: 204-212
38 Avrim Blum, Alan M. Frieze, Ravi Kannan, Santosh Vempala: A Polynomial-Time Algorithm for Learning Noisy Linear Threshold Functions. FOCS 1996: 330-338
37 Alan M. Frieze, Mark Jerrum, Ravi Kannan: Learning Linear Transformations. FOCS 1996: 359-368
1995
36 Ravi Kannan, László Lovász, Miklós Simonovits: Isoperimetric Problems for Convex Bodies and a Localization Lemama. Discrete & Computational Geometry 13: 541-559 (1995)
1994
35 Ravi Kannan: Markov Chains and Polynomial Time Algorithms FOCS 1994: 656-671
1993
34 Avrim Blum, Ravi Kannan: Learning an Intersection of k Halfspaces over a Uniform Distribution FOCS 1993: 312-320
33 Ravi Kannan: Optimal solution and value of parametric integer programs. IPCO 1993: 11-21
32 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. Combinatorics, Probability & Computing 2: 271-284 (1993)
31 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)
1992
30 Egon Balas, Gérard Cornuéjols, Ravi Kannan: Proceedings of the 2nd Integer Programming and Combinatorial Optimization Conference, Pittsburgh, PA, May 1992 Carnegie Mellon University 1992
29 William J. Cook, Mark Hartmann, Ravi Kannan, Colin McDiarmid: On integer points in polyhedra. Combinatorica 12(1): 27-37 (1992)
28 Ravi Kannan: Lattice translates of a polytope and the Frobenius problem. Combinatorica 12(2): 161-177 (1992)
1991
27 David Applegate, Ravi Kannan: Sampling and Integration of Near Log-Concave functions STOC 1991: 156-163
26EEMartin 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)
1990
25 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
24 William J. Cook, Ravi Kannan, Alexander Schrijver: Chvátal Closures for mixed Integer Programming Problems. Math. Program. 47: 155-174 (1990)
1989
23EERavi Kannan: The Frobenius Problem. FSTTCS 1989: 242-251
22 Martin E. Dyer, Alan M. Frieze, Ravi Kannan: A Random Polynomial Time Algorithm for Approximating the Volume of Convex Bodies STOC 1989: 375-381
21 Zvi Galil, Ravi Kannan, Endre Szemerédi: On 3-pushdown graphs with large separators. Combinatorica 9(1): 9-19 (1989)
20 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)
19 Merrick L. Furst, Ravi Kannan: Succinct Certificates for Almost All Subset Sum Problems. SIAM J. Comput. 18(3): 550-558 (1989)
1988
18 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): 262-280 (1988)
1987
17 Rex A. Dwyer, Ravi Kannan: Convex Hull of Randomly Chosen Points from A Polytope. Parallel Algorithms and Architectures 1987: 16-24
16 Ravindran Kannan, Gary L. Miller, Larry Rudolph: Sublinear Parallel Algorithm for Computing the Greatest Common Divisor of Two Integers. SIAM J. Comput. 16(1): 7-16 (1987)
1986
15EERavi Kannan, László Lovász: Covering Minima and Lattice Point Free Convex Bodies. FSTTCS 1986: 193-213
14EERavi Kannan: Basis Reduction and Evidence for Transcendence of Certain Numbers. FSTTCS 1986: 263-269
13 Zvi Galil, Ravi Kannan, Endre Szemerédi: On Nontrivial Separators for k-Page Graphs and Simulations by Nondeterministic One-Tape Turing Machines STOC 1986: 39-49
12EERavindran Kannan, Richard J. Lipton: Polynomial-time algorithm for the orbit problem. J. ACM 33(4): 808-821 (1986)
1985
11 Ravi Kannan: Unraveling k-page graphs Information and Control 66(1/2): 1-5 (1985)
1984
10 Alan M. Frieze, Ravi Kannan, J. C. Lagarias: Linear Congruential Generators Do Not Produce Random Sequences FOCS 1984: 480-484
9 Ravindran Kannan, Gary L. Miller, Larry Rudolph: Sublinear Parallel Algorithm for Computing the Greatest Common Divisor of Two Integers FOCS 1984: 7-11
8 Ravindran Kannan, Arjen K. Lenstra, László Lovász: Polynomial Factorization and Nonrandomness of Bits of Algebraic and Some Transcendental Numbers STOC 1984: 191-200
7 Ravindran Kannan: Towards Separating Nondeterminism from Determinism. Mathematical Systems Theory 17(1): 29-45 (1984)
1983
6 Ravi Kannan: Improved Algorithms for Integer Programming and Related Lattice Problems STOC 1983: 193-206
5 Ravi Kannan: Alternation and the Power of Nondeterminism STOC 1983: 344-346
4EERavindran Kannan: Polynomial-Time Aggregation of Integer Programming Problems J. ACM 30(1): 133-145 (1983)
1980
3 Ravindran Kannan, Richard J. Lipton: The Orbit Problem is Decidable STOC 1980: 252-261
2EERavindran Kannan: A Polynomial Algorithm for the Two-Variable Integer Programming Problem. J. ACM 27(1): 118-122 (1980)
1979
1 Ravindran Kannan, Achim Bachem: Polynomial Algorithms for Computing the Smith and Hermite Normal Forms of an Integer Matrix. SIAM J. Comput. 8(4): 499-507 (1979)

Coauthor Index

1Ankit Aggarwal [93]
2Noga Alon [57] [61] [62]
3David Applegate [27]
4Sanjeev Arora [58]
5Achim Bachem [1]
6Egon Balas [30]
7Avrim Blum [34] [38] [43] [46]
8Andreas Brieden [48]
9Kevin L. Chang [80]
10David Cheng [72] [79]
11Monojit Choudhury [90] [92]
12William J. Cook [24] [29]
13Gérard Cornuéjols [30]
14Evgeny Dantsin [60]
15Anirban Dasgupta [81] [83]
16Amit Deshpande [86] [93]
17Nikhil R. Devanur [88]
18Petros Drineas [55] [59] [63] [65] [71] [74] [75] [76] [85]
19Rex A. Dwyer [17]
20Martin E. Dyer [22] [26] [32] [42]
21Alan M. Frieze [10] [18] [22] [26] [32] [37] [38] [40] [46] [47] [52] [53] [55] [65] [66] [87]
22Merrick L. Furst [19]
23Zvi Galil [13] [20] [21]
24Andreas Goerdt [60]
25Peter Gritzmann [48]
26Mark Hartmann [29]
27Johan Håstad [18]
28Edward A. Hirsch [60]
29John E. Hopcroft [81] [83]
30Mark Jerrum [37]
31Ajai Kapoor [32]
32Marek Karpinski [57] [61] [62] [70] [77]
33Victor Klee [48]
34Jon M. Kleinberg [60]
35Jeffrey C. Lagarias (J. C. Lagarias) [10] [18]
36Arjen K. Lenstra [8]
37Guangxing Li [39]
38Richard J. Lipton [3] [12]
39László Lovász [8] [15] [36] [41] [48] [54] [78]
40Michael W. Mahoney [64] [71] [74] [75] [76] [85]
41Colin McDiarmid (Colin J. H. McDiarmid) [29]
42Gary L. Miller [9] [16]
43Pradipta Prometheus Mitra [81] [83]
44Ravi Montenegro [64] [78]
45John Mount [42]
46Animesh Mukherjee [90] [92]
47Hariharan Narayanan [91]
48Andreas Nolte [49] [50]
49Christos H. Papadimitriou [60]
50Ljubomir Perkovic [32]
51William R. Pulleyblank [25]
52Prabhakar Raghavan [60]
53Larry Rudolph [9] [16]
54Hadi Salmasian [68] [73] [84]
55A. Das Sarma [86]
56Uwe Schöning [60]
57Alexander Schrijver [24]
58Adi Shamir [18]
59Miklós Simonovits [36] [41] [48]
60Endre Szemerédi [13] [20] [21]
61Prasad Tetali [45] [51]
62Thorsten Theobald [69] [82]
63Umesh V. Vazirani [32]
64Wenceslas Fernandez de la Vega [57] [61] [62] [70] [77]
65Santosh Vempala [38] [44] [45] [46] [47] [51] [55] [56] [65] [66] [67] [68] [70] [72] [73] [79] [84] [89]
66H. Venkateswaran [31]
67Adrian Vetta [56] [67]
68V. Vinay [31] [55] [65]
69Grant Wang [72] [79]
70Andrew Chi-Chih Yao [31]

Colors in the list of coauthors

Copyright © Tue Nov 3 08:52:44 2009 by Michael Ley (ley@uni-trier.de)