Pseudorandom bits for non-commutative programs

DOI10.4230/LIPICS.CCC.2025.9MaRDI QIDQ7296757zbMATH OpenFDO

Authors Chin Ho Lee, Emanuele Viola

Publication date 14 July 2026

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.CCC.2025.9

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Cites work

• Bounded independence plus noise fools products
• Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
• Cryptography in NC^0
• Faster isomorphism for p-groups of class 2 and exponent p
• Fourier bounds and pseudorandom generators for product tests
• Fourier growth of regular branching programs
• Generalizations of Fourier analysis, and how to apply them
• scientific article; zbMATH DE number 44579 (Why is no real title available?)
• scientific article; zbMATH DE number 3552764 (Why is no real title available?)
• scientific article; zbMATH DE number 1318047 (Why is no real title available?)
• scientific article; zbMATH DE number 1970438 (Why is no real title available?)
• scientific article; zbMATH DE number 7561734 (Why is no real title available?)
• scientific article; zbMATH DE number 7829312 (Why is no real title available?)
• Improved pseudorandom generators for combinatorial rectangles
• Iterative construction of Cayley expander graphs
• More on bounded independence plus noise: pseudorandom generators for read-once polynomials
• On the power of small-depth computation
• Paradigms for Unconditional Pseudorandom Generators
• Pseudorandom Bit Generators That Fool Modular Sums
• Pseudorandom bits for polynomials
• Pseudorandom generators for \(CC^0[p]\) and the Fourier spectrum of low-degree polynomials over finite fields
• Pseudorandom generators for combinatorial checkerboards
• Pseudorandom generators for combinatorial shapes
• Pseudorandom generators for group products, extended abstract
• Pseudorandom generators for read-once branching programs, in any order
• Pseudorandom generators for width-3 branching programs
• Pseudorandom generators from polarizing random walks
• Pseudorandomness
• Pseudorandomness for regular branching programs via Fourier analysis
• Pseudorandomness via the discrete Fourier transform
• Pseudorandomness via the discrete Fourier transform
• Semi-direct product in groups and zig-zag product in graphs: connections and applications
• Simple Constructions of Almost k-wise Independent Random Variables
• Small-Bias Probability Spaces: Efficient Constructions and Applications
• Small-Bias Spaces for Group Products
• The coin problem for product tests
• The sum of \(D\) small-bias generators fools polynomials of degree \(D\)
• Unconditional pseudorandom generators for low degree polynomials

This page was built for publication: Pseudorandom bits for non-commutative programs

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