Pseudorandom generators from polarizing random walks

DOI10.4086/TOC.2019.V015A010MaRDI QIDQ5204828zbMATH OpenOpenAlexFDO

Authors Eshan Chattopadhyay, Pooya Hatami, Kaave Hosseini, Shachar Lovett

Publication date 5 December 2019

Published in Theory of Computing (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4086/toc.2019.v015a010

zbMATH Keywords

pseudorandom generatorrandom walk

Mathematics Subject Classification ID

Boolean functions (06E30) Sums of independent random variables; random walks (60G50) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Randomized algorithms (68W20)

Recommendations

• scientific article; zbMATH DE number 7250141
• Pseudorandom generators for low sensitivity functions
• Pseudorandom generators for low degree polynomials

Cited in

(11)

• A random-walk pseudorandom byte generator
• Pseudorandomness via the discrete Fourier transform
• Pseudorandom generators for low sensitivity functions
• scientific article; zbMATH DE number 7528580 (Why is no real title available?)
• Pseudorandom Generators from the Second Fourier Level and Applications to AC0 with Parity Gates
• scientific article; zbMATH DE number 7250141 (Why is no real title available?)
• Paradigms for Unconditional Pseudorandom Generators
• Near-optimal derandomization of medium-width branching programs
• Quantum cryptography in Algorithmica
• Pseudorandomness, symmetry, smoothing: I
• Pseudorandom generators for unbounded-width permutation branching programs

This page was built for publication: Pseudorandom generators from polarizing random walks

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