2026-07-22T14:20:23Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:23709 2025-10-27T10:42:41Z ddc:004 open_access

Algebraic Pseudorandomness in VNC⁰ Andrews, Robert Polynomial identity testing Algebraic circuits Ideal Proof System We study the arithmetic complexity of hitting set generators, which are pseudorandom objects used for derandomization of the polynomial identity testing problem. We give new explicit constructions of hitting set generators whose outputs are computable in VNC⁰, i.e., can be computed by arithmetic formulas of constant size. Unconditionally, we construct a VNC⁰-computable generator that hits arithmetic circuits of constant depth and polynomial size. We also give conditional constructions, under strong but plausible hardness assumptions, of VNC⁰-computable generators that hit arithmetic formulas and arithmetic branching programs of polynomial size, respectively. As a corollary of our constructions, we derive lower bounds for subsystems of the Geometric Ideal Proof System of Grochow and Pitassi. Constructions of such generators are implicit in prior work of Kayal on lower bounds for the degree of annihilating polynomials. Our main contribution is a construction whose correctness relies on circuit complexity lower bounds rather than degree lower bounds. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Robert Andrews 2025 Is Part Of LIPIcs, Volume 339, 40th Computational Complexity Conference (CCC 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CCC.2025.15 urn:nbn:de:0030-drops-237092 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2025.15 eng https://creativecommons.org/licenses/by/4.0/legalcode