Deterministic equivalence test of multilinear polynomials with coefficients 0 or 1 I know that there's no known poly-time equivalence testing algorithm for polynomials of $n$ variables(also called identity test) when the polynomials are given as circuit. Notice that when the polynomial is given in the canonical form this problem is trivial, but when it's given as a circuit it's there's no known poly-time algorithm to solve it.
I wanted to know if the same problem in the case of multilinear polynomials ($n$ variables) with coefficients in $\{0,1\}$ can be solved in poly-time? A multilinear polynomial is one polynomial of degree $\leq n$ and in each product of the polynomial, each variable can be multiplied at most one time.
For example, $x_1 +x_2x_3 +x_1x_3$ is a multilinear polynomial with coef. in $\{0,1\}$, but $2x_1$ is just multilinear. Furthermore, $x_1^2$ is not multilinear.
EDIT: Polynomial equivalence is not known to be "difficult" (as I previously stated) but neither is known to be poly-time solvable.
 A: The decision problem of polynomial identity testing is closely related to the reconstruction of a polynomial from its evaluations.  In particular an algorithm that determines equality or not of any two polynomials must in the worst case (that the polynomials are equal) use evaluations at a set of assignments sufficient to exactly reconstruct that polynomial (by a standard adversary argument, although the work to do the reconstruction can be omitted).
The restrictions on the polynomials considered here (multilinear, monic terms) make the problem equivalent to one of "hidden hypergraphs", namely searching for a family of subsets of the given variables $x_1,\ldots,x_n$ (corresponding to those that are multiplied to form each individual term of such polynomials).
The literature contains as of 2010 a survey that the reconstruction of hidden hypergraphs from edge-counting queries with deterministic polynomial complexity is an open problem.  However edge-counting queries amount to using binary (0/1) assignments for the variables, and the computational queries considered here are stronger (assignments of arbitrary integer arguments, if I understand correctly).
We can show that if arbitrarily large integer arguments are used, a single assignment suffices to distinguish (test the identity of) any two polynomials.  While deterministic, such an algorithm cannot be called "polynomial complexity" as the evaluations will have bit-lengths $2^n$ for $n$ variables.  Hence the final comparison of those will require exponential time.
One can also show that the family of all $2^n$ assignments of binary $x_i \in \{0,1\}$ suffices to distinguish any two nonidentical polynomials here.  However that in the worst case requires exponentially many such queries.
Between those extremes there remains a lot of room for investigation.  I'm interested to summarize the required queries for smallish numbers of variables, to see if a trend can be discerned.  I will have to post more later on this.
