The Complexity of Distributions
From MaRDI portal
Publication:2884580
DOI10.1137/100814998zbMath1255.68077MaRDI QIDQ2884580
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
sampling; distribution; lower bound; decision tree; pseudorandom generator; succinct data structure; local
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68P05: Data structures
Related Items
On Lipschitz Bijections Between Boolean Functions, Bounded Independence Plus Noise Fools Products, Sampling Lower Bounds: Boolean Average-Case and Permutations, Unnamed Item, On mappings on the hypercube with small average stretch, Bounded-depth circuits cannot sample good codes, Local expanders, Bi-Lipschitz bijection between the Boolean cube and the Hamming ball, Fine-Grained Cryptography, Bounded Indistinguishability and the Complexity of Recovering Secrets