The complexity of distributions

DOI10.1137/100814998zbMATH Open1255.68077OpenAlexW2166853092MaRDI QIDQ2884580FDOQ2884580

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

samplingdistributiondecision treelower boundsuccinct data structurelocalpseudorandom generator

Mathematics Subject Classification ID

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

Cited In (18)

• Malign distributions for average case circuit complexity
• Sampling Lower Bounds: Boolean Average-Case and Permutations
• Bounded-depth circuits cannot sample good codes
• Bounded Indistinguishability and the Complexity of Recovering Secrets
• Title not available (Why is that?)
• On Lipschitz Bijections Between Boolean Functions
• Bounded Independence Plus Noise Fools Products
• On mappings on the hypercube with small average stretch
• An approximate distribution for the maximum order complexity
• Local expanders
• On the complexity of circulations
• Fine-Grained Cryptography
• Title not available (Why is that?)
• Title not available (Why is that?)
• Non-malleable codes with optimal rate for poly-size circuits
• Bi-Lipschitz bijection between the Boolean cube and the Hamming ball
• Title not available (Why is that?)
• The Complexity and Distribution of Hard Problems

   Recommendations

• Sampling Lower Bounds: Boolean Average-Case and Permutations 👍 👎
• Bounded-depth circuits cannot sample good codes 👍 👎
• On the complexity of finite random functions 👍 👎
• Randomness buys depth for approximate counting 👍 👎
• Sampling algorithms 👍 👎

This page was built for publication: The complexity of distributions

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