Sampling Lower Bounds: Boolean Average-Case and Permutations

DOI10.1137/18M1198405zbMath1435.68092MaRDI QIDQ5216796

Emanuele Viola

Publication date: 20 February 2020

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

zbMATH Keywords

permutationssamplingdistributionlower boundextractorsconstant-depth circuitsdata structureswitching lemmaBoolean average-casepolarizing min-entropy

Mathematics Subject Classification ID

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

Related Items (2)

Unnamed Item ⋮ Sampling Lower Bounds: Boolean Average-Case and Permutations

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Succinct representations of permutations and functions
• Bounded-depth circuits cannot sample good codes
• \(\Sigma_ 1^ 1\)-formulae on finite structures
• Random oracles separate PSPACE from the polynomial-time hierarchy
• The cell probe complexity of succinct data structures
• Efficient cryptographic schemes provably as secure as subset sum
• Bi-Lipschitz bijection between the Boolean cube and the Hamming ball
• Bounded Indistinguishability and the Complexity of Recovering Secrets
• Changing base without losing space
• The Complexity of Distributions
• On the randomness complexity of efficient sampling
• Random Permutations using Switching Networks
• Extractors for Turing-Machine Sources
• Parity, circuits, and the polynomial-time hierarchy
• Concentration Inequalities and Martingale Inequalities: A Survey
• On the Redundancy of Succinct Data Structures
• On the Size of Succinct Indices
• Constructive Proofs of Concentration Bounds
• Randomized Distributed Edge Coloring via an Extension of the Chernoff--Hoeffding Bounds
• On Universal Classes of Extremely Random Constant-Time Hash Functions
• Bit-Probe Lower Bounds for Succinct Data Structures
• Quadratic Maps Are Hard to Sample
• Pseudorandom Generators with Optimal Seed Length for Non-Boolean Poly-Size Circuits
• An efficient reduction from two-source to non-malleable extractors: achieving near-logarithmic min-entropy
• Analysis of Boolean Functions
• On the Correlation of Parity and Small-Depth Circuits
• Exponential separation between shallow quantum circuits and unbounded fan-in shallow classical circuits
• Sampling Lower Bounds: Boolean Average-Case and Permutations
• Pseudorandomness from Shrinkage
• Poly-logarithmic Frege depth lower bounds via an expander switching lemma
• Explicit two-source extractors and resilient functions
• Bounded Independence Fools Halfspaces
• Extractors for Circuit Sources
• Extractors and Lower Bounds for Locally Samplable Sources

This page was built for publication: Sampling Lower Bounds: Boolean Average-Case and Permutations