A PSPACE construction of a hitting set for the closure of small algebraic circuits

DOI10.1145/3188745.3188792zbMath1428.68171arXiv1712.09967OpenAlexW2963746686MaRDI QIDQ5230372

Amir Shpilka, Michael A. Forbes

Publication date: 22 August 2019

Published in: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1712.09967

zbMATH Keywords

arithmetic circuitsPSPACEpolynomial identity testingexplicit constructionalgebraic circuitshitting-set

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Networks and circuits as models of computation; circuit complexity (68Q06)

Related Items (3)

A note on VNP-completeness and border complexity ⋮ Complete decomposition of symmetric tensors in linear time and polylogarithmic precision ⋮ Blackbox identity testing for sum of special ROABPs and its border class

This page was built for publication: A PSPACE construction of a hitting set for the closure of small algebraic circuits