Near-optimal bootstrapping of hitting sets for algebraic models

DOI10.4086/TOC.2023.V019A012MaRDI QIDQ6138075zbMATH OpenFDO

Authors Mrinal Kumar, Ramprasad Saptharishi, Anamay Tengse

Publication date 16 January 2024

Published in Theory of Computing (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

bootstrappingderandomizationpolynomial identity testingalgebraic circuitshardness-randomness

Mathematics Subject Classification ID

Randomized algorithms (68W20) Symbolic computation and algebraic computation (68W30) Networks and circuits as models of computation; circuit complexity (68Q06)

Recommendations

• Near-optimal bootstrapping of hitting sets for algebraic circuits
• Bootstrapping variables in algebraic circuits
• Bootstrapping variables in algebraic circuits
• Derandomization from Algebraic Hardness
• A PSPACE construction of a hitting set for the closure of small algebraic circuits

This page was built for publication: Near-optimal bootstrapping of hitting sets for algebraic models

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6138075)