Please note: This master’s thesis presentation will take place in DC 2310 and online.
Omkar Baraskar, Master’s candidate
David R. Cheriton School of Computer Science
Supervisors: Professors Éric Schost, Rafael Oliveira
Given a list of monomials of a n-variate polynomial f and an integer s, decide whether there exists a invertible transform A such that f(Ax) has less than s monomials. This problem is called the Equivalence testing to sparse polynomials (ETsparse). It was studied in [Grigoriev, Karpinski 93] over Q, in this work, they give an exponential in n^4 time algorithm for the problem. The lack of progress in the complexity of the problem over last three decades raises a question, is ETsparse hard? In this thesis we give an affirmative answer to the question by showing that it is NP-hard over any field.
Sparse orbit complexity of a polynomial f is the smallest integer s_0 such that there exists an invertible transform A such that f(Ax) has s_0 monomials. Since ETsparse is NP-hard hence computing the sparse orbit complexity is also NP-hard. We also show that approximating the sparse orbit complexity up to a factor of s_f^{1/3-e} for any e belonging to (0,1/3) is NP-hard, where s_f is the number of monomials in f. Interestingly, this approximation result has been shown without invoking the celebrated PCP theorem.
To attend this master’s thesis presentation in person, please go to DC 2310. You can also attend virtually on Zoom.