The Polynomial Equivalence (PE) problem asks to check if two given multivariate polynomials are equivalent. Polynomials f(x) and g(x) are equivalent if there is an invertible matrix A such that f = g(Ax). Equivalent polynomials represent the same function up to a change in the coordinate system. Much is unknown about the exact complexity of PE, which is an algebraic analog of the graph isomorphism problem.
A natural variant of PE is the equivalence testing (ET) problem. The ET problem for a class C of polynomials asks to decide if a given f is equivalent to some g in C. Efficient ET algorithms are known for several natural classes of polynomials.
In the talk, we will discuss the complexity of deciding if a given polynomial f is equivalent to some s-sparse polynomial, where the parameter s is also given. A polynomial is s-sparse if it has at most s monomials. We will show that this problem is NP-hard. Moreover, it is also NP-hard to approximate (within a "small" factor) the smallest s such that f is equivalent to some s-sparse polynomial. If time permits, we will also discuss an NP-hardness result for testing equivalence to low-support polynomials.
Based on joint work with Omkar Baraskar, Agrim Dewan, and Pulkit Sinha.
Short Bio:
Chandan Saha is a faculty member in the Department of Computer Science and Automation at the Indian Institute of Science (IISc). He did his PhD and MTech at IIT Kanpur and BE at Jadavpur University. He was a postdoctoral fellow at the Max Planck Institute for Informatics before joining IISc in 2012. His research is primarily on problems in algebraic complexity theory.
