Marginal hitting sets imply super-polynomial lower bounds for permanent
Maurice J. Jansen, Rahul Santhanam · 2012
Suppose f is a univariate polynomial of degree r = r(n) that is computed by a size n arithmetic circuit. It is a basic fact of algebra that a nonzero univariate polynomial of degree r can vanish on at most r points. This implies that for checking whether f is identically zero, it suffices to query f on an arbitrary test set of r + 1 points. Could this brute-force method be improved upon by a single point? We develop a framework where such a marginal improvement implies that Permanent does not have polynomial size arithmetic circuits.