A Polynomial Time Constructible Hitting Set for Restricted 1-Branching Programs of Width 3

DOI10.1007/978-3-540-69507-3_45MaRDI QIDQ5448802zbMATH OpenOpenAlexFDO

Authors Jiří Šíma, Stanislav Zak

Publication date 7 March 2008

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-69507-3_45

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Recommendations

• A polynomial-time construction of a hitting set for read-once branching programs of width 3
• A Sufficient Condition for Sets Hitting the Class of Read-Once Branching Programs of Width 3
• Almost k-wise independent sets establish hitting sets for width-3 1-branching programs
• Hitting sets with near-optimal error for read-once branching programs
• New lower bounds and hierarchy results for restricted branching programs

Cited in

(6)

• A Sufficient Condition for Sets Hitting the Class of Read-Once Branching Programs of Width 3
• Almost k-wise independent sets establish hitting sets for width-3 1-branching programs
• Length of polynomials over finite groups
• A PSPACE construction of a hitting set for the closure of small algebraic circuits
• Hitting sets for multilinear read-once algebraic branching programs, in any order
• A polynomial-time construction of a hitting set for read-once branching programs of width 3

This page was built for publication: A Polynomial Time Constructible Hitting Set for Restricted 1-Branching Programs of Width 3

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