Ravi Kannan

Ravindran Kannan

	2012
110		Sanjeev Arora, Rong Ge, Ravindran Kannan, Ankur Moitra: Computing a nonnegative matrix factorization - provably. STOC 2012: 145-162
	2011
109		Sanjeev Arora, Rong Ge, Ravi Kannan, Ankur Moitra: Computing a Nonnegative Matrix Factorization -- Provably CoRR abs/1111.0952: (2011)
108		Ravi Kannan: Algorithms: Recent Highlights and Challenges. SIGARCH Computer Architecture News 39(3): (2011)
	2010
107		Amit Kumar, Ravindran Kannan: Clustering with Spectral Norm and the k-Means Algorithm. FOCS 2010: 299-308
106		Ravindran Kannan: Spectral methods for matrices and tensors. STOC 2010: 1-12
105		Ravindran Kannan: Spectral Methods for Matrices and Tensors CoRR abs/1004.1253: (2010)
104		Amit Kumar, Ravindran Kannan: Clustering with Spectral Norm and the k-means Algorithm CoRR abs/1004.1823: (2010)
	2009
103		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 Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik 2009
102		Ankit Aggarwal, Amit Deshpande, Ravi Kannan: Adaptive Sampling for k-Means Clustering. APPROX-RANDOM 2009: 15-28
101		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
100		Ravindran Kannan: A New Probability Inequality Using Typical Moments and Concentration Results. FOCS 2009: 211-220
99		Ravi Kannan, K. Narayan Kumar: Preface -- IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (2009). FSTTCS 2009
98		Ravi Kannan, Hariharan Narayanan: Random walks on polytopes and an affine interior point method for linear programming. STOC 2009: 561-570
97		Atish Das Sarma, Amit Deshpande, Ravi Kannan: Finding Dense Subgraphs in G(n, 1/2). WAOA 2009: 98-103
96		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)
95		Ravi Kannan, Santosh Vempala: Spectral Algorithms. Foundations and Trends in Theoretical Computer Science 4(3-4): 157-288 (2009)
94		Ravi Kannan, Luis Rademacher: Optimization of a convex program with a polynomial perturbation. Oper. Res. Lett. 37(6): 384-386 (2009)
93		Kevin L. Chang, Ravi Kannan: Pass-Efficient Algorithms for Learning Mixtures of Uniform Distributions. SIAM J. Comput. 39(3): 783-812 (2009)
	2008
92		Nikhil R. Devanur, Ravi Kannan: Market Equilibria in Polynomial Time for Fixed Number of Goods or Agents. FOCS 2008: 45-53
91		Alan M. Frieze, Ravi Kannan: A new approach to the planted clique problem. FSTTCS 2008: 187-198
90		Atish Das Sarma, Amit Deshpande, Ravi Kannan: Finding Dense Subgraphs in G(n,1/2) CoRR abs/0807.5111: (2008)
89		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)
88		Ravindran Kannan, Hadi Salmasian, Santosh Vempala: The Spectral Method for General Mixture Models. SIAM J. Comput. 38(3): 1141-1156 (2008)
	2007
87		Anirban Dasgupta, John E. Hopcroft, Ravi Kannan, Pradipta Prometheus Mitra: Spectral clustering with limited independence. SODA 2007: 1036-1045
86		Ravi Kannan, Thorsten Theobald: Games of fixed rank: a hierarchy of bimatrix games. SODA 2007: 1124-1132
	2006
85		Anirban Dasgupta, John E. Hopcroft, Ravi Kannan, Pradipta Prometheus Mitra: Spectral Clustering by Recursive Partitioning. ESA 2006: 256-267
84		Kevin L. Chang, Ravi Kannan: The space complexity of pass-efficient algorithms for clustering. SODA 2006: 1157-1166
83		David Cheng, Ravi Kannan, Santosh Vempala, Grant Wang: A divide-and-merge methodology for clustering. ACM Trans. Database Syst. 31(4): 1499-1525 (2006)
82		Ravi Kannan, László Lovász, Ravi Montenegro: Blocking Conductance and Mixing in Random Walks. Combinatorics, Probability & Computing 15(4): 541-570 (2006)
81		Wenceslas Fernandez de la Vega, Ravi Kannan, Marek Karpinski: Approximation of Global MAX-CSP Problems. Electronic Colloquium on Computational Complexity (ECCC) 13(124): (2006)
80		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)
79		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)
78		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)
	2005
77		Ravindran Kannan, Hadi Salmasian, Santosh Vempala: The Spectral Method for General Mixture Models. COLT 2005: 444-457
76		David Cheng, Santosh Vempala, Ravi Kannan, Grant Wang: A divide-and-merge methodology for clustering. PODS 2005: 196-205
75		Petros Drineas, Ravi Kannan, Michael W. Mahoney: Sampling Sub-problems of Heterogeneous Max-cut Problems and Approximation Algorithms. STACS 2005: 57-68
74		Wenceslas Fernandez de la Vega, Marek Karpinski, Ravi Kannan, Santosh Vempala: Tensor decomposition and approximation schemes for constraint satisfaction problems. STOC 2005: 747-754
73		Ravi Kannan, Thorsten Theobald: Games of fixed rank: A hierarchy of bimatrix games CoRR abs/cs/0511021: (2005)
	2004
72		Hadi Salmasian, Ravindran Kannan, Santosh Vempala: The Spectral Method for Mixture Models Electronic Colloquium on Computational Complexity (ECCC)(067): (2004)
71		Ravi Kannan, Santosh Vempala, Adrian Vetta: On clusterings: Good, bad and spectral. J. ACM 51(3): 497-515 (2004)
70		Alan M. Frieze, Ravi Kannan, Santosh Vempala: Fast monte-carlo algorithms for finding low-rank approximations. J. ACM 51(6): 1025-1041 (2004)
69		Petros 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
68		Ravi Kannan, Michael W. Mahoney, Ravi Montenegro: Rapid Mixing of Several Markov Chains for a Hard-Core Model. ISAAC 2003: 663-675
67		Petros Drineas, Ravi Kannan: Pass efficient algorithms for approximating large matrices. SODA 2003: 223-232
66		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)
	2002
65		Noga Alon, Wenceslas Fernandez de la Vega, Ravi Kannan, Marek Karpinski: Random sampling and approximation of MAX-CSP problems. STOC 2002: 232-239
64		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
63		Petros Drineas, Ravi Kannan: Fast Monte-Carlo Algorithms for Approximate Matrix Multiplication. FOCS 2001: 452-459
62		Sanjeev Arora, Ravi Kannan: Learning mixtures of arbitrary gaussians. STOC 2001: 247-257
61		Noga 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
60		Ravi Kannan, Santosh Vempala, Adrian Vetta: On Clusterings - Good, Bad and Spectral. FOCS 2000: 367-377
	1999
59		Petros Drineas, Alan M. Frieze, Ravi Kannan, Santosh Vempala, V. Vinay: Clustering in Large Graphs and Matrices. SODA 1999: 291-299
58		László Lovász, Ravi Kannan: Faster Mixing via Average Conductance. STOC 1999: 282-287
57		Alan M. Frieze, Ravi Kannan: Quick Approximation to Matrices and Applications. Combinatorica 19(2): 175-220 (1999)
56		Alan M. Frieze, Ravi Kannan: A Simple Algorithm for Constructing Szemere'di's Regularity Partition. Electr. J. Comb. 6: (1999)
55		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
54		Ravi Kannan, Andreas Nolte: A Fast Random Greedy Algorithm for the Component Commonality Problem. ESA 1998: 223-234
53		Ravi Kannan, Andreas Nolte: Local Search in Smooth Convex Sets. FOCS 1998: 218-226
52		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
51		Alan M. Frieze, Ravi Kannan, Santosh Vempala: Fast Monte-Carlo Algorithms for Finding Low-Rank Approximations. FOCS 1998: 370-378
50		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
49		Ravi Kannan, Prasad Tetali, Santosh Vempala: Simple Markov-Chain Algorithms for Generating Bipartite Graphs and Tournaments (Extended Abstract). SODA 1997: 193-200
48		Ravi Kannan, Santosh Vempala: Sampling Lattice Points. STOC 1997: 696-700
47		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)
46		Martin E. Dyer, Ravi Kannan, John Mount: Sampling contingency tables. Random Struct. Algorithms 10(4): 487-506 (1997)
45		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
44		Alan M. Frieze, Ravi Kannan: The Regularity Lemma and Approximation Schemes for Dense Problems. FOCS 1996: 12-20
43		Ravi Kannan, Guangxing Li: Sampling According to the Multivariate Normal Density. FOCS 1996: 204-212
42		Avrim Blum, Alan M. Frieze, Ravi Kannan, Santosh Vempala: A Polynomial-Time Algorithm for Learning Noisy Linear Threshold Functions. FOCS 1996: 330-338
41		Alan M. Frieze, Mark Jerrum, Ravi Kannan: Learning Linear Transformations. FOCS 1996: 359-368
	1995
40		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
39		Ravi Kannan: Markov Chains and Polynomial Time Algorithms FOCS 1994: 656-671
	1993
38		Avrim Blum, Ravi Kannan: Learning an Intersection of k Halfspaces over a Uniform Distribution FOCS 1993: 312-320
37		Ravi Kannan: Optimal solution and value of parametric integer programs. IPCO 1993: 11-21
36		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)
35		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
34		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
33		William J. Cook, Mark Hartmann, Ravi Kannan, Colin McDiarmid: On integer points in polyhedra. Combinatorica 12(1): 27-37 (1992)
32		Ravi Kannan: Lattice translates of a polytope and the Frobenius problem. Combinatorica 12(2): 161-177 (1992)
	1991
31		David Applegate, Ravi Kannan: Sampling and Integration of Near Log-Concave functions STOC 1991: 156-163
30		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)
	1990
29		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
28		William J. Cook, Ravi Kannan, Alexander Schrijver: Chvátal Closures for mixed Integer Programming Problems. Math. Program. 47: 155-174 (1990)
	1989
27		Ravi Kannan: The Frobenius Problem. FSTTCS 1989: 242-251
26		Martin E. Dyer, Alan M. Frieze, Ravi Kannan: A Random Polynomial Time Algorithm for Approximating the Volume of Convex Bodies STOC 1989: 375-381
25		Zvi Galil, Ravi Kannan, Endre Szemerédi: On 3-pushdown graphs with large separators. Combinatorica 9(1): 9-19 (1989)
24		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)
23		Merrick L. Furst, Ravi Kannan: Succinct Certificates for Almost All Subset Sum Problems. SIAM J. Comput. 18(3): 550-558 (1989)
	1988
22		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
21		Rex A. Dwyer, Ravi Kannan: Convex Hull of Randomly Chosen Points from A Polytope. Parallel Algorithms and Architectures 1987: 16-24
20		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
19		Ravi Kannan, László Lovász: Covering Minima and Lattice Point Free Convex Bodies. FSTTCS 1986: 193-213
18		Ravi Kannan: Basis Reduction and Evidence for Transcendence of Certain Numbers. FSTTCS 1986: 263-269
17		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
16		Ravindran Kannan, Richard J. Lipton: Polynomial-time algorithm for the orbit problem. J. ACM 33(4): 808-821 (1986)
	1985
15		Ravi Kannan: Unraveling k-page graphs Information and Control 66(1/2): 1-5 (1985)
14		Ravindran Kannan: Solving Systems of Linear Equations over Polynomials. Theor. Comput. Sci. 39: 69-88 (1985)
	1984
13		Alan M. Frieze, Ravi Kannan, J. C. Lagarias: Linear Congruential Generators Do Not Produce Random Sequences FOCS 1984: 480-484
12		Ravindran Kannan, Gary L. Miller, Larry Rudolph: Sublinear Parallel Algorithm for Computing the Greatest Common Divisor of Two Integers FOCS 1984: 7-11
11		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
10		Ravindran Kannan: Towards Separating Nondeterminism from Determinism. Mathematical Systems Theory 17(1): 29-45 (1984)
	1983
9		Ravi Kannan: Improved Algorithms for Integer Programming and Related Lattice Problems STOC 1983: 193-206
8		Ravi Kannan: Alternation and the Power of Nondeterminism STOC 1983: 344-346
7		Ravindran Kannan: Polynomial-Time Aggregation of Integer Programming Problems J. ACM 30(1): 133-145 (1983)
	1982
6		Ravi Kannan: Circuit-Size Lower Bounds and Non-Reducibility to Sparse Sets Information and Control 55(1-3): 40-56 (1982)
	1981
5		Ravi Kannan: Towards Separating Nondeterministic Time from Deterministic Time FOCS 1981: 235-243
4		Ravi Kannan: A Circuit-Size Lower Bound FOCS 1981: 304-309
	1980
3		Ravindran Kannan, Richard J. Lipton: The Orbit Problem is Decidable STOC 1980: 252-261
2		Ravindran 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

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

Colors in the list of coauthors

Last update Sat Jun 2 20:57:36 2012 CET by the DBLP Team — Data released under the ODC-BY 1.0 license — See also our legal information page