We provide a list of new natural VNP-intermediate polynomial
families, based on basic (combinatorial) NP-complete problems that
are complete under \emph{parsimonious} reductions. Over finite
fields, these families are in VNP, and under the plausible
hypothesis $\text{Mod}_pP \not\subseteq P/\text{poly}$, are neither VNP-hard (even under
oracle-circuit reductions) nor in VP. Prior to ... more >>>

Newton iteration (NI) is an almost 350 years old recursive formula that approximates a simple root of a polynomial quite rapidly. We generalize it to a matrix recurrence (allRootsNI) that approximates all the roots simultaneously. In this form, the process yields a better circuit complexity in the case when the ... more >>>

Border complexity captures polynomials that can be approximated arbitrarily well by small algebraic circuits, and debordering asks how efficiently such an approximation can be converted into an exact computation. Debordering lies at the heart of the gap between Valiant's determinant versus permanent conjecture and its strengthening by Mulmuley and Sohoni ... more >>>

I give a short proof that the border determinantal complexity of F_n = x_1^n + ... + x_n^n over C is at least (n-1)^2/(4e), and at least (n-1)^2/(2e) in the symmetric model. The same argument shows that the border determinantal complexity of x_1^d + ... + x_N^d is Theta(Nd) for ... more >>>