Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR25-062 | 13th May 2025 14:57

Lower Bounds from Succinct Hitting Sets

RSS-Feed




TR25-062
Authors: Prerona Chatterjee, Anamay Tengse
Publication: 13th May 2025 18:22
Downloads: 85
Keywords: 


Abstract:

We investigate the consequences of the existence of ``efficiently describable'' hitting sets for polynomial sized algebraic circuit (VP), in particular, \emph{VP-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 \neq VNP, or yield a fairly strong lower bound against TC^0 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
$\mathcal{C}$, is essentially the same as proving a separation between $\mathcal{C}$ and VPSPACE: the algebraic analogue of PSPACE. More formally, we prove an upper bound on \emph{equations} for polynomial sized algebraic circuits(VP), in terms of VPSPACE.
Using the same upper bound, we also show that even \emph{sub-polynomially explicit hitting sets} for --- much weaker than VP-succinct hitting sets that are almost polylog-explicit --- would imply that either VP \neq VNP or that P \neq PSPACE. This motivates us to define the concept of \emph{cryptographic hitting sets}, which we believe is interesting on its own.



ISSN 1433-8092 | Imprint