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

DOI10.1007/978-3-642-27660-6_33zbMATH Open1302.68118OpenAlexW1245159845MaRDI QIDQ2891385FDOQ2891385

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

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

Mathematics Subject Classification ID

Cites Work

• Hardness vs randomness
• Simple Constructions of Almost k-wise Independent Random Variables
• Branching Programs and Binary Decision Diagrams
• Improved pseudorandom generators for depth 2 circuits
• Pseudorandom generators for space-bounded computation
• Pseudorandomness for width-2 branching programs
• Pseudorandom generators for group products
• 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 beating the hybrid argument
• Pseudorandom generators for regular branching programs

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)