2023/09/14 by Chatterjee, Prerona, Tengse, Anamay · 1 citation
#Computational Complexity (cs.CC) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2309.07612
We investigate the consequences of the existence of ``efficiently describable'' hitting sets for polynomial sized algebraic circuit (VP), in particular, \emphVP-succinct hitting sets. Existence of such hitting sets is known to be equivalent to a ``natural-proofs-barrier'' towards algebraic circuit lower bounds, from the works that introduced this concept (Forbes \etal (2018), Grochow \etal (2017)). We show that the existence of VP-succinct hitting sets for VP would either imply that VP ≠ VNP, or yield a fairly strong lower bound against TC0 circuits, assuming the Generalized Riemann Hypothesis (GRH). This result is a consequence of showing that designing efficiently describable (VP-explicit) hitting set generators for a class C, is essentially the same as proving a separation between C and VPSPACE: the algebraic analogue of \textsfPSPACE. More formally, we prove an upper bound on equations for polynomial sized algebraic circuits (VP), in terms of VPSPACE. Using the same upper bound, we also show that even sub-polynomially explicit hitting sets for VP -- much weaker than VP-succinct hitting sets that are almost polylog-explicit -- would imply that either VP ≠ VNP or that P ≠ PSPACE. This motivates us to define the concept of cryptographic hitting sets, which we believe is interesting on its own.