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

DOI10.1007/978-3-540-69507-3_45zbMATH Open1132.68033OpenAlexW1577143859MaRDI QIDQ5448802FDOQ5448802

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

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

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Cited In (6)

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