The average sensitivity of bounded-depth circuits
From MaRDI portal
Publication:290255
DOI10.1016/S0020-0190(97)00131-2zbMath1337.68124OpenAlexW2088559598MaRDI QIDQ290255
Publication date: 1 June 2016
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/s0020-0190(97)00131-2
Related Items
Separation results for Boolean function classes ⋮ On mappings on the hypercube with small average stretch ⋮ Expander-based cryptography meets natural proofs ⋮ Lipschitz bijections between boolean functions ⋮ Pseudo-average block sensitivity equals average sensitivity ⋮ Bi-Lipschitz bijection between the Boolean cube and the Hamming ball ⋮ Approximating Boolean Functions with Depth-2 Circuits ⋮ Bounds on the Fourier coefficients of the weighted sum function ⋮ The average sensitivity of bounded-depth formulas ⋮ On the nonlinearity of the sequence of signs of Kloosterman sums ⋮ Boolean nested canalizing functions: a comprehensive analysis ⋮ The influence of canalization on the robustness of Boolean networks ⋮ On the average sensitivity of the weighted sum function ⋮ Quantum Talagrand, KKL and Friedgut's theorems and the learnability of quantum Boolean functions ⋮ Paradigms for Unconditional Pseudorandom Generators ⋮ Collectively canalizing Boolean functions ⋮ Learning $$AC^0$$ Under k-Dependent Distributions ⋮ The Fourier Entropy–Influence Conjecture for Certain Classes of Boolean Functions ⋮ Bounded-depth circuits cannot sample good codes ⋮ Noise sensitivity of Boolean functions and applications to percolation ⋮ Unnamed Item ⋮ A note on the entropy/influence conjecture ⋮ Homomorphic Evaluation Requires Depth ⋮ On extremal \(k\)-CNF formulas ⋮ The simplified weighted sum function and its average sensitivity ⋮ A Fixed-Depth Size-Hierarchy Theorem for $\mathrm{AC}^0[\oplus$ via the Coin Problem] ⋮ Unnamed Item ⋮ Variable Influences in Conjunctive Normal Forms ⋮ Ehrenfeucht-Fraïssé Games on Random Structures ⋮ Criticality of regular formulas ⋮ Prediction from partial information and hindsight, with application to circuit lower bounds ⋮ Harmonicity and invariance on slices of the Boolean cube ⋮ Complexity measures and decision tree complexity: a survey. ⋮ Circuit and decision tree complexity of some number theoretic problems ⋮ Pseudorandom Functions: Three Decades Later
Cites Work
- Unnamed Item
- \(\Sigma_ 1^ 1\)-formulae on finite structures
- The computational complexity of universal hashing
- Method of determining lower bounds for the complexity of \(\Pi\)-circuits
- Constant depth circuits, Fourier transform, and learnability
- Parity, circuits, and the polynomial-time hierarchy
- Limiting Negations in Constant Depth Circuits
