103 citations · 199 across the 15 of their papers we have counts for
16 papers
Random Separating Hyperplane Theorem and Learning Polytopes
Chiranjib Bhattacharyya, Ravindran Kannan, Amit Kumar
The Separating Hyperplane theorem is a fundamental result in Convex Geometry with myriad applications. Our first result, Random Separating Hyperplane Theorem (RSH), is a strengthen…
Bit Complexity of Jordan Normal Form and Spectral Factorization
Papri Dey, Ravi Kannan, Nick Ryder +1
We study the bit complexity of two related fundamental computational problems in linear algebra and control theory. Our results are: (1) An $\tilde{O}(n^{ω+3}a+n^4a^2+n^ω\log(1/ε))…
Learning a Latent Simplex in Input-Sparsity Time
Ainesh Bakshi, Chiranjib Bhattacharyya, Ravi Kannan +2
We consider the problem of learning a latent -vertex simplex , given access to , which can be viewed as a data matrix with …
Finding a latent k-simplex in O(k . nnz(data)) time via Subset Smoothing
Chiranjib Bhattacharyya, Ravindran Kannan
In this paper we show that a large class of Latent variable models, such as Mixed Membership Stochastic Block(MMSB) Models, Topic Models, and Adversarial Clustering, can be unified…
Chi-squared Amplification: Identifying Hidden Hubs
Ravi Kannan, Santosh Vempala
We consider the following general hidden hubs model: an random matrix with a subset of special rows (hubs): entries in rows outside are generated from…
A provable SVD-based algorithm for learning topics in dominant admixture corpus
Trapit Bansal, Chiranjib Bhattacharyya, Ravindran Kannan
Topic models, such as Latent Dirichlet Allocation (LDA), posit that documents are drawn from admixtures of distributions over words, known as topics. The inference problem of recov…