We study some problems solvable in deterministic polynomial time given oracle access to the (promise version of) the Arthur-Merlin class.
Our main results are the following: (i) BPP^{NP}_{||} \subseteq P^{prAM}_{||}; (ii) S_2^p \subseteq P^{prAM}. In addition to providing new upperbounds for the classes S_2^p and BPP^{NP}_{||}, these results are interesting ... more >>>

Consider a homogeneous degree d polynomial f = T_1 + \cdots + T_s, T_i = g_i(\ell_{i,1}, \ldots, \ell_{i, m}) where g_i's are homogeneous m-variate degree d polynomials and \ell_{i,j}'s are linear polynomials in n variables. We design a (randomized) learning algorithm that given black-box access to f, computes black-boxes for ... more >>>

We present a general framework for designing efficient algorithms for unsupervised learning problems, such as mixtures of Gaussians and subspace clustering. Our framework is based on a meta algorithm that learns arithmetic circuits in the presence of noise, using lower bounds. This builds upon the recent work of Garg, Kayal ... more >>>

We present a deterministic 2^{k^{\mathcal{O}(1)}} \text{poly}(n,d) time algorithm for decomposing d-dimensional, width-n tensors of rank at most k over \mathbb{R} and \mathbb{C}. This improves upon the previous randomized algorithm of Peleg, Shpilka, and Volk (ITCS '24) that takes 2^{k^{k^{\mathcal{O}(k)}}} \text{poly}(n,d) time and the deterministic n^{k^k} time algorithms of Bhargava, Saraf, ... more >>>