Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR23-135 | 13th May 2025 15:22

Lower Bounds from Succinct Hitting Sets

RSS-Feed




Revision #1
Authors: Prerona Chatterjee, Anamay Tengse
Accepted on: 13th May 2025 15:22
Downloads: 22
Keywords: 


Abstract:

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



Changes to previous version:

Improved the consequences of the previous statement.


Paper:

TR23-135 | 14th September 2023 13:47

On Annihilators of Explicit Polynomial Maps





TR23-135
Authors: Prerona Chatterjee, Anamay Tengse
Publication: 14th September 2023 23:28
Downloads: 475
Keywords: 


Abstract:

We study the algebraic complexity of annihilators of polynomials maps. In particular, when a polynomial map is `encoded by' a small algebraic circuit, we show that the coefficients of an annihilator of the map can be computed in PSPACE. Even when the underlying field is that of reals or complex numbers, an analogous statement is true. We achieve this by using the class VPSPACE, that coincides with computability of coefficients in PSPACE over integers.

As a consequence, we derive the following two conditional results. First, we show that a VP-explicit hitting set generator for ''all of'' VP would separate either VP from VNP, or non-uniform P from PSPACE. Second, in relation to algebraic natural proofs, we show that proving an algebraic natural proofs barrier would imply either VP $\neq$ VNP or DSPACE($\log^{\log^{\ast}n} n$) $\not\subset$ P.



ISSN 1433-8092 | Imprint