Quadratic Maps Are Hard to Sample

DOI10.1145/2934308zbMath1427.68109MaRDI QIDQ4973863

Emanuele Viola

Publication date: 6 December 2019

Published in: ACM Transactions on Computation Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/2934308

zbMATH Keywords

sampling; polynomials; extractors; complexity of distributions

Mathematics Subject Classification ID

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

68Q87: Probability in computer science (algorithm analysis, random structures, phase transitions, etc.)

Related Items

Sampling Lower Bounds: Boolean Average-Case and Permutations, Unnamed Item