Abstract:A multivariate polynomial on $n$ variables $x_1,\ldots,x_n$ of total degree $n$ over $\mathbf{Z}_2$ containing the multilinear monomial $\prod_{i=1}^n x_i$ is by the combinatorial nullstellensatz [Alon, Comb. Probab. Comput., 1999] known to always have a nonroot. We show that there cannot be a randomised polynomial time algorithm that given an arithmetic circuit of polynomial size formally computing such a polynomial, locates a nonroot with constant nonzero probability unless RP=NP. The result holds even when the individual degree of every variable in the input polynomial is at most two.
From: Andreas Björklund [view email]
[v1]
Sun, 7 Jun 2026 14:23:23 UTC (17 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。