Almost k-Wise Independent Sets Establish Hitting Sets for Width-3 1-Branching Programs

DOI10.1007/978-3-642-20712-9_10zbMath1330.68126OpenAlexW1652911975MaRDI QIDQ3007622

Jiří Šíma, Stanislav Zak

Publication date: 17 June 2011

Published in: Computer Science – Theory and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-20712-9_10

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Data structures (68P05) Randomized algorithms (68W20)

Related Items (7)

A Sufficient Condition for Sets Hitting the Class of Read-Once Branching Programs of Width 3 ⋮ Simple Optimal Hitting Sets for Small-Success RL ⋮ Pseudorandom Pseudo-distributions with Near-Optimal Error for Read-Once Branching Programs ⋮ Small-bias is not enough to hit read-once CNF ⋮ Unnamed Item ⋮ Near-optimal pseudorandom generators for constant-depth read-once formulas ⋮ A Polynomial-Time Construction of a Hitting Set for Read-Once Branching Programs of Width 3

Cites Work

• Unnamed Item
• Pseudorandom generators for space-bounded computation
• Hardness vs randomness
• Pseudorandom Generators for Polynomial Threshold Functions
• A Sufficient Condition for Sets Hitting the Class of Read-Once Branching Programs of Width 3
• 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
• 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: Almost k-Wise Independent Sets Establish Hitting Sets for Width-3 1-Branching Programs