We design a deterministic algorithm that, given blackbox access to the product $f=\prod_{i=1}^{\ell}{h_i}$ of $\ell$ irreducible $s$-sparse $n$-variate polynomials of bounded individual degree $d$, over fields of characteristic zero, and more generally over fields of sufficiently large positive characteristic, recovers the $h_i$'s and their multiplicities in time $\mathrm{poly}(n,(s\ell d)^d)$. ... more >>>

The Hamiltonian Cycle polynomial, denoted as $HC_n$, is defined to be the sum of the weighted Hamiltonian Cycles in an $n$-vertex complete digraph, with vertices labeled $1$ to $n$ and edges weighted by formal variables $x_{i,j}$. The Permanent and $HC$, defined as the family $\{HC_n | \ n \geq 1\}$, ... more >>>

We introduce an approach to distinguishing isomorphism types of graphs based on vector spaces of polynomials that are set-wise invariant under permutations (“separating modules,” which are representations of the symmetric group), inspired by the Geometric Complexity Theory approach to separating complexity classes (Mulmuley & Sohoni, SIAM J. Comput., 2001). We ... more >>>