Pseudorandom Pseudo-distributions with Near-Optimal Error for Read-Once Branching Programs
From MaRDI portal
Publication:5130845
DOI10.1137/18M1197734zbMath1453.68211OpenAlexW3007807100MaRDI QIDQ5130845
Mark Braverman, Sumegha Garg, Gil Cohen
Publication date: 29 October 2020
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/18m1197734
Analysis of algorithms and problem complexity (68Q25) Data structures (68P05) Randomized algorithms (68W20) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)
Related Items
Paradigms for Unconditional Pseudorandom Generators ⋮ Simple Optimal Hitting Sets for Small-Success RL ⋮ Complexity theory. Abstracts from the workshop held November 14--20, 2021 (hybrid meeting) ⋮ Unnamed Item ⋮ Unnamed Item ⋮ A Polynomial-Time Construction of a Hitting Set for Read-Once Branching Programs of Width 3
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Pseudorandom generators for space-bounded computation
- \(\text{BP}_{\text{H}}\text{SPACE}(S) \subseteq \text{DSPACE}(S^{3/2})\)
- \(\text{RL}\subseteq \text{SC}\)
- Hardness vs randomness
- Entropy waves, the zig-zag graph product, and new constant-degree expanders
- In search of an easy witness: Exponential time vs. probabilistic polynomial time.
- Randomness is linear in space
- On approximating the eigenvalues of stochastic matrices in probabilistic logspace
- Relationships between nondeterministic and deterministic tape complexities
- Pseudorandomness for network algorithms
- On recycling the randomness of states in space bounded computation
- Pseudorandom Generators for Combinatorial Shapes
- Pseudorandomness for Regular Branching Programs via Fourier Analysis
- Pseudorandom walks on regular digraphs and the RL vs. L problem
- Almost k-Wise Independent Sets Establish Hitting Sets for Width-3 1-Branching Programs
- A Sample of Samplers: A Computational Perspective on Sampling
- Pseudorandomness for Linear Length Branching Programs and Stack Machines
- Pseudorandom Generators for Regular Branching Programs
- Undirected connectivity in log-space
- An $O(\logn \log\logn)$ Space Algorithm for Undirected st-Connectivity
- Parallel computation for well-endowed rings and space-bounded probabilistic machines
- Tiny families of functions with random properties: A quality-size trade-off for hashing
- Pseudorandomness from Shrinkage
- Computational Complexity
- An O (log( n ) 4/3 ) space algorithm for ( s, t ) connectivity in undirected graphs
- Pseudorandom generators for group products
- Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
- Pseudorandomness for Read-Once Formulas
- Derandomizing polynomial identity tests means proving circuit lower bounds
This page was built for publication: Pseudorandom Pseudo-distributions with Near-Optimal Error for Read-Once Branching Programs
