A Polynomial-Time Construction of a Hitting Set for Read-Once Branching Programs of Width 3

DOI10.3233/FI-2021-2101MaRDI QIDQ5862347

Stanislav Zak, Jiří Šíma

Publication date: 9 March 2022

Published in: Fundamenta Informaticae (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2101.01151

zbMATH Keywords

derandomizationbounded widthhitting setread-once branching programalmost k-wise independent set

Mathematics Subject Classification ID

Computer science (68-XX)

Related Items (2)

Paradigms for Unconditional Pseudorandom Generators ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Pseudorandom generators for combinatorial checkerboards
• Small-bias is not enough to hit read-once CNF
• Pseudorandom generators for space-bounded computation
• Randomization, approximation, and combinatorial optimization. Algorithms and techniques. 3rd international workshop on Randomization and approximation techniques in computer science, and 2nd international workshop on Approximation algorithms for combinatorial optimization problems RANDOM-APPROX '99. Berkeley, CA, USA, August 8--11, 1999. Proceedings
• Hardness vs randomness
• Pseudorandom Generators for Polynomial Threshold Functions
• Pseudorandomness for Regular Branching Programs via Fourier Analysis
• 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
• Pseudorandom Generators for Regular Branching Programs
• Improved Pseudorandom Generators for Depth 2 Circuits
• Simple Constructions of Almost k-wise Independent Random Variables
• Branching Programs and Binary Decision Diagrams
• Near-optimal pseudorandom generators for constant-depth read-once formulas
• Simple Optimal Hitting Sets for Small-Success RL
• Pseudorandom Pseudo-distributions with Near-Optimal Error for Read-Once Branching Programs
• Pseudorandom generators for width-3 branching programs
• Hitting sets for multilinear read-once algebraic branching programs, in any order
• Pseudorandom generators for group products
• A Polynomial Time Constructible Hitting Set for Restricted 1-Branching Programs of Width 3

This page was built for publication: A Polynomial-Time Construction of a Hitting Set for Read-Once Branching Programs of Width 3