Hitting sets with near-optimal error for read-once branching programs

DOI10.1145/3188745.3188780zbMath1427.68095OpenAlexW2809259539MaRDI QIDQ5230302

Gil Cohen, Sumegha Garg, Mark Braverman

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://doi.org/10.1145/3188745.3188780

zbMATH Keywords

derandomizationhitting setsread-once branching programsspace-bounded computation

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Randomized algorithms (68W20)

Related Items (2)

Limitations of the Impagliazzo-Nisan-Wigderson pseudorandom generator against permutation branching programs ⋮ Improved Explicit Hitting-Sets for ROABPs

This page was built for publication: Hitting sets with near-optimal error for read-once branching programs