A Sufficient Condition for Sets Hitting the Class of Read-Once Branching Programs of Width 3

DOI10.1007/978-3-642-27660-6_33MaRDI QIDQ2891385zbMATH OpenOpenAlexFDO

Authors Jiří Šíma, Stanislav Zak

Publication date 15 June 2012

Published in SOFSEM 2012: Theory and Practice of Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-27660-6_33

Mathematics Subject Classification ID

Recommendations

• A polynomial-time construction of a hitting set for read-once branching programs of width 3
• On the read-once property of branching programs and CNFs of bounded treewidth
• A Polynomial Time Constructible Hitting Set for Restricted 1-Branching Programs of Width 3
• Almost \(k\)-wise independent sets establish hitting sets for width-3 1-branching programs
• On Tseitin formulas, read-once branching programs and treewidth
• On Tseitin formulas, read-once branching programs and treewidth
• scientific article; zbMATH DE number 549860
• A lower bound for read-once-only branching programs
• scientific article; zbMATH DE number 1759451
• A read-once lower bound and a \((1,+k)\)-hierarchy for branching programs

Cites work

• A Polynomial Time Constructible Hitting Set for Restricted 1-Branching Programs of Width 3
• Almost \(k\)-wise independent sets establish hitting sets for width-3 1-branching programs
• Branching Programs and Binary Decision Diagrams
• Hardness vs randomness
• Improved pseudorandom generators for depth 2 circuits
• On beating the hybrid argument
• Pseudorandom generators for group products, extended abstract
• Pseudorandom generators for regular branching programs
• Pseudorandom generators for space-bounded computation
• Pseudorandomness for width-2 branching programs
• Simple Constructions of Almost k-wise Independent Random Variables

Cited in

(5)

• Pseudorandom generators for combinatorial checkerboards
• 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 Polynomial Time Constructible Hitting Set for Restricted 1-Branching Programs of Width 3
• A polynomial-time construction of a hitting set for read-once branching programs of width 3

This page was built for publication: A Sufficient Condition for Sets Hitting the Class of Read-Once Branching Programs of Width 3

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