On sums of INW pseudorandom generators

DOI10.4230/LIPICS.APPROX/RANDOM.2025.67MaRDI QIDQ7346900zbMATH OpenFDO

Authors William M. Hoza

Publication date 11 September 2026

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.APPROX/RANDOM.2025.67

Mathematics Subject Classification ID

Randomized algorithms (68W20) Approximation algorithms (68W25) Combinatorial optimization (90C27)

Cites work

• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Computational Indistinguishability Amplification: Tight Product Theorems for System Composition
• Error reduction for weighted PRGs against read once branching programs
• Graph streaming lower bounds for parameter estimation and property testing via a streaming XOR lemma
• Hitting sets for regular branching programs
• scientific article; zbMATH DE number 6351503 (Why is no real title available?)
• scientific article; zbMATH DE number 1301964 (Why is no real title available?)
• scientific article; zbMATH DE number 1306886 (Why is no real title available?)
• scientific article; zbMATH DE number 1559537 (Why is no real title available?)
• scientific article; zbMATH DE number 7768373 (Why is no real title available?)
• Title not available (Why is no real title available?)
• Inverse-exponential correlation bounds and extremely rigid matrices from a new derandomized XOR lemma
• Limitations of the Impagliazzo-Nisan-Wigderson pseudorandom generator against permutation branching programs
• On recycling the randomness of states in space bounded computation
• On the power of regular and permutation branching programs
• Paradigms for Unconditional Pseudorandom Generators
• Pseudodistributions that beat all pseudorandom generators (extended abstract)
• Pseudorandom bits for polynomials
• Pseudorandom generators for group products, extended abstract
• Pseudorandom generators for read-once branching programs, in any order
• Pseudorandom generators for regular branching programs
• Pseudorandom generators for space-bounded computation
• Pseudorandom generators for unbounded-width permutation branching programs
• Pseudorandom generators for width-3 branching programs
• Pseudorandom pseudo-distributions with near-optimal error for read-once branching programs
• Pseudorandomness
• Pseudorandomness for network algorithms
• Pseudorandomness for width-2 branching programs
• Randomness is linear in space
• Recursive error reduction for regular branching programs
• Simple Constructions of Almost k-wise Independent Random Variables
• Simple optimal hitting sets for small-success RL
• Small-Bias Probability Spaces: Efficient Constructions and Applications
• Small-Bias Spaces for Group Products
• Some limitations of the sum of small-bias distributions
• Space pseudorandom generators by communication complexity lower bounds
• The coin problem and pseudorandomness for branching programs
• The sum of \(D\) small-bias generators fools polynomials of degree \(D\)
• Unconditional pseudorandom generators for low degree polynomials
• Undirected connectivity in log-space
• Weighted pseudorandom generators via inverse analysis of random walks and shortcutting

This page was built for publication: On sums of INW pseudorandom generators

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7346900)