Sampling Lower Bounds: Boolean Average-Case and Permutations
From MaRDI portal
Publication:5216796
DOI10.1137/18M1198405zbMath1435.68092MaRDI QIDQ5216796
Publication date: 20 February 2020
Published in: SIAM Journal on Computing (Search for Journal in Brave)
permutationssamplingdistributionlower boundextractorsconstant-depth circuitsdata structureswitching lemmaBoolean average-casepolarizing min-entropy
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)
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