Near-optimal derandomization of medium-width branching programs
From MaRDI portal
Cites work
- scientific article; zbMATH DE number 1301964 (Why is no real title available?)
- scientific article; zbMATH DE number 7561753 (Why is no real title available?)
- scientific article; zbMATH DE number 7650109 (Why is no real title available?)
- scientific article; zbMATH DE number 7768373 (Why is no real title available?)
- Derandomization beyond connectivity: undirected Laplacian systems in nearly logarithmic space
- Entropy waves, the zig-zag graph product, and new constant-degree expanders
- Error reduction for weighted PRGs against read once branching programs
- Improved pseudorandomness for unordered branching programs through local monotonicity
- Pseudodistributions that beat all pseudorandom generators (extended abstract)
- Pseudorandom generators for space-bounded computation
- Pseudorandom generators for width-3 branching programs
- Pseudorandom generators from polarizing random walks
- Pseudorandom pseudo-distributions with near-optimal error for read-once branching programs
- Pseudorandomness for network algorithms
- Randomness is linear in space
- Relationships between nondeterministic and deterministic tape complexities
- Simple optimal hitting sets for small-success RL
- \(\text{BP}_{\text{H}}\text{SPACE}(S) \subseteq \text{DSPACE}(S^{3/2})\)
Cited in
(3)
This page was built for publication: Near-optimal derandomization of medium-width branching programs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6499213)
