Sampling lower bounds: Boolean average-case and permutations

DOI10.1137/18M1198405MaRDI QIDQ5216796zbMATH OpenFDO

Authors Emanuele Viola

Publication date 20 February 2020

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

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

zbMATH Keywords

samplingpermutationsdistributiondata structurelower boundextractorsconstant-depth circuitsswitching lemmaBoolean average-casepolarizing min-entropy

Mathematics Subject Classification ID

Data structures (68P05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Networks and circuits as models of computation; circuit complexity (68Q06)

Recommendations

• The complexity of distributions
• Bounded-depth circuits cannot sample good codes
• Extractors and lower bounds for locally samplable sources
• AC0 unpredictability
• Extractors and lower bounds for locally samplable sources

Cites work

• scientific article; zbMATH DE number 3162894 (Why is no real title available?)
• scientific article; zbMATH DE number 6538681 (Why is no real title available?)
• scientific article; zbMATH DE number 176751 (Why is no real title available?)
• scientific article; zbMATH DE number 6931784 (Why is no real title available?)
• A satisfiability algorithm for \(\mathrm{AC}^0\)
• An efficient reduction from two-source to non-malleable extractors: achieving near-logarithmic min-entropy
• Analysis of Boolean Functions
• Bi-Lipschitz bijection between the Boolean cube and the Hamming ball
• Bit-probe lower bounds for succinct data structures
• Bounded Independence Fools Halfspaces
• Bounded indistinguishability and the complexity of recovering secrets
• Bounded-depth circuits cannot sample good codes
• Cell probe lower bounds for succinct data structures
• Cell-probe lower bounds for succinct partial sums
• Changing base without losing space
• Concentration Inequalities and Martingale Inequalities: A Survey
• Constructive proofs of concentration bounds
• Efficient cryptographic schemes provably as secure as subset sum
• Explicit two-source extractors and resilient functions
• Exponential separation between shallow quantum circuits and unbounded fan-in shallow classical circuits
• Extractors and lower bounds for locally samplable sources
• Extractors for Turing-machine sources
• Extractors for circuit sources
• In-place sparse suffix sorting
• On Universal Classes of Extremely Random Constant-Time Hash Functions
• On the Correlation of Parity and Small-Depth Circuits
• On the Redundancy of Succinct Data Structures
• On the Size of Succinct Indices
• On the randomness complexity of efficient sampling
• Parity, circuits, and the polynomial-time hierarchy
• Poly-logarithmic Frege depth lower bounds via an expander switching lemma
• Pseudorandom generators with optimal seed length for non-Boolean poly-size circuits
• Pseudorandomness from shrinkage
• Quadratic Maps Are Hard to Sample
• Random oracles separate PSPACE from the polynomial-time hierarchy
• Random permutations using switching networks
• Randomized Distributed Edge Coloring via an Extension of the Chernoff--Hoeffding Bounds
• Sampling lower bounds: Boolean average-case and permutations
• Succinct representations of permutations and functions
• The cell probe complexity of succinct data structures
• The complexity of distributions
• \(\Sigma_ 1^ 1\)-formulae on finite structures

Cited in

(7)

• Average-case lower bounds for the plurality problem
• The complexity of distributions
• Sampling lower bounds: Boolean average-case and permutations
• scientific article; zbMATH DE number 7650118 (Why is no real title available?)
• Bi-Lipschitz bijection between the Boolean cube and the Hamming ball
• Sampling, flowers and communication
• Range avoidance for low-depth circuits and connections to pseudorandomness

This page was built for publication: Sampling lower bounds: Boolean average-case and permutations

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