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

random walkpseudorandom generator

Mathematics Subject Classification ID

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

Recommendations

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

Cited in

(8)

• A random-walk pseudorandom byte generator
• Pseudorandom generators for low sensitivity functions
• Paradigms for Unconditional Pseudorandom Generators
• scientific article; zbMATH DE number 7528580 (Why is no real title available?)
• scientific article; zbMATH DE number 7250141 (Why is no real title available?)
• Near-optimal derandomization of medium-width branching programs
• Quantum cryptography in Algorithmica
• Pseudorandomness via the discrete Fourier transform

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)