6 citations · 10 across the 10 of their papers we have counts for
11 papers
Learning Read-Once Determinants and the Principal Minor Assignment Problem
Abhiram Aravind, Abhranil Chatterjee, Sumanta Ghosh +3
A symbolic determinant under rank-one restriction computes a polynomial of the form , where are square matrices over a field $\…
NP-hardness of testing equivalence to sparse polynomials and to constant-support polynomials
Omkar Baraskar, Agrim Dewan, Chandan Saha +1
An -sparse polynomial has at most monomials with nonzero coefficients. The Equivalence Testing problem for sparse polynomials (ETsparse) asks to decide if a given polynomial…
Low-depth arithmetic circuit lower bounds via shifted partials
Prashanth Amireddy, Ankit Garg, Neeraj Kayal +2
We prove super-polynomial lower bounds for low-depth arithmetic circuits using the shifted partials measure [Gupta-Kamath-Kayal-Saptharishi, CCC 2013], [Kayal, ECCC 2012] and the a…
Randomized polynomial-time equivalence between determinant and trace-IMM equivalence tests
Janaky Murthy, Vineet Nair, Chandan Saha
Equivalence testing for a polynomial family {g_m} over a field F is the following problem: Given black-box access to an n-variate polynomial f(x), where n is the number of variable…
Learning sums of powers of low-degree polynomials in the non-degenerate case
Ankit Garg, Neeraj Kayal, Chandan Saha
We develop algorithms for writing a polynomial as sums of powers of low degree polynomials. Consider an -variate degree- polynomial which can be written as $$f = c_1Q_1^{…
Quasi-polynomial Hitting-set for Set-depth-Delta Formulas
Manindra Agrawal, Chandan Saha, Nitin Saxena
We call a depth-4 formula C set-depth-4 if there exists a (unknown) partition (X_1,...,X_d) of the variable indices [n] that the top product layer respects, i.e. C(x) = \sum_{i=1}^…