The Complexity of Distributions

DOI10.1137/100814998zbMath1255.68077OpenAlexW2166853092MaRDI QIDQ2884580

Emanuele Viola

Publication date: 30 May 2012

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/100814998

zbMATH Keywords

samplingdistributionlower bounddecision treepseudorandom generatorsuccinct data structurelocal

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Data structures (68P05)

Related Items (10)

On mappings on the hypercube with small average stretch ⋮ Bi-Lipschitz bijection between the Boolean cube and the Hamming ball ⋮ Local expanders ⋮ Unnamed Item ⋮ On Lipschitz Bijections Between Boolean Functions ⋮ Bounded Independence Plus Noise Fools Products ⋮ Bounded-depth circuits cannot sample good codes ⋮ Sampling Lower Bounds: Boolean Average-Case and Permutations ⋮ Fine-Grained Cryptography ⋮ Bounded Indistinguishability and the Complexity of Recovering Secrets

This page was built for publication: The Complexity of Distributions