Towards a tight hardness–randomness connection between permanent and arithmetic circuit identity testing

We make progress towards proving an equivalence between the problem of derandomization of arithmetic circuit identity testing (ACIT), and the arithmetic circuit complexity of the permanent defined by pern=∑σ∈Sn∏i=1nxiσ(i). We develop an ACIT-based derandomization hypothesis, and show this is a necessary   condition for proving that permanent has super-polynomial arithmetic circuits over fields of characteristic zero. Informally, this hypothesis poses the existence of a subexponential size hitting set computable by subexponential size uniform TC0TC0 circuits against size n arithmetic circuits with multilinear output. Assuming the Generalized Riemann Hypothesis (GRH), we show that this hypothesis is sufficient   for proving that either permanent does not have polynomial size (nonuniform) arithmetic circuits, or that the Boolean circuit class uniform TC0TC0 is strictly contained in uniform NC2NC2.

► We investigate arithmetic circuit identity testing and the complexity of the permanent. ► We give a necessary condition for proving that permanent has super-polynomial arithmetic circuit size. ► We show that this condition implies the disjunction of an arithmetic and boolean lower bound.