Efficiently check if two large factorized multivariate polynomials are the same without expansion Given two large multivariate polynomials $f$ and $g$ in $m$ variables of degree $n$, which are factorized and have i.e. more than a 1000 terms, how can we check efficiently if they are the same?
To compare the coefficients, one would need to compute the coefficients, but I think expanding the polynomials can lead to too many terms to compute in reasonable time. Is there a smarter way? Or is this impossible because it is a necessity to check all coefficients?
 A: Two UNIVARIATE polynomials of degree $n$ are identical, if they coincide at $n+1$ places, for example at the numbers $0,...,n$. 
To formulate it more mathematically, if $f(n)=g(n)$ for $n=0,...,d\ $ and $deg(f)=deg(g)=d\ $, then we can conculde $f=g$.
This can be easily checked even for monster polynomials.
If we have two variables (lets say $x$ and $y$), we can fix $x$ and get a univariate polynomial. If the polynomial has degree $d$ with respect to $x$, I think we can also use the above idea, but I am not sure, whether it actually works.
If yes, we could use the method for arbitary polynomials.
In practice you could also do the following : 
Evaluate the difference of the polynomials at some random points. 
If the value is not $0$ at any point, the polynomials must be distinct. 
If you get $0$ at all the points, you have a very good chance that the polynomials are equal. 
Maybe, from a mathematical point of view, this method is debateable. But it should be sufficient for practical purpose.
A: That essentially means that you want to solve the notoriously hard problem of polynomial identity testing in a setting where the polynomials are given as algebraic circuits (consisting of "formulas" for the factors). Any progress there is warmly welcome, because a large community of world-class researchers hardly made any breakthroughs in the past dozen years or so, at least from a practical perspective. To the best of my knowledge, it's also one of the big, big open problems where we do not even have a good idea about its place in the computational complexity hierarchy except for highly restricted settings.
Peter's idea is that you should evaluate and compare both polynomials on an unisolvent point set such as the Padua points. Unfortunately, determining a (small) such set is non-trivial in general, to say the least.
The practitioner's solution to that: rely on the Schwartz-Zippel lemma and plug in as many random points as necessary until the probability of a false positive is low enough. E.g., $10^{-10}$ times your estimate on the combined probability that there is a sudden earthquake destroying your machine, a bit flip due to radiation, a compiler bug that spoils some fancier algorithm, or (if all that's too small) the probability that you introduce a bug while you implement or design that algorithm...
Seriously.
