The complexity of distributions

DOI10.1137/100814998MaRDI QIDQ2884580zbMATH OpenOpenAlexFDO

Authors 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)

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: lower bounds and applications

Cited in

(18)

• scientific article; zbMATH DE number 4129950 (Why is no real title available?)
• scientific article; zbMATH DE number 6474904 (Why is no real title available?)
• On mappings on the hypercube with small average stretch
• An approximate distribution for the maximum order complexity
• Local expanders
• Fine-Grained Cryptography
• Bounded indistinguishability and the complexity of recovering secrets
• On the complexity of circulations
• Bounded independence plus noise fools products
• scientific article; zbMATH DE number 7650118 (Why is no real title available?)
• Sampling lower bounds: Boolean average-case and permutations
• scientific article; zbMATH DE number 1875916 (Why is no real title available?)
• The Complexity and Distribution of Hard Problems
• Non-malleable codes with optimal rate for poly-size circuits
• Bi-Lipschitz bijection between the Boolean cube and the Hamming ball
• Bounded-depth circuits cannot sample good codes
• On Lipschitz bijections between Boolean functions
• Malign distributions for average case circuit complexity

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)