The average sensitivity of bounded-depth circuits
From MaRDI portal
Publication:290255
DOI10.1016/S0020-0190(97)00131-2zbMATH Open1337.68124OpenAlexW2088559598MaRDI QIDQ290255FDOQ290255
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
Recommendations
Cites Work
- \(\Sigma_ 1^ 1\)-formulae on finite structures
- Constant depth circuits, Fourier transform, and learnability
- Parity, circuits, and the polynomial-time hierarchy
- The computational complexity of universal hashing
- Method of determining lower bounds for the complexity of \(\Pi\)-circuits
- Limiting Negations in Constant Depth Circuits
- Title not available (Why is that?)
Cited In (38)
- Robust topology optimization for periodic structures by combining sensitivity averaging with a semianalytical method
- Circuit and decision tree complexity of some number theoretic problems
- A Fixed-Depth Size-Hierarchy Theorem for $\mathrm{AC}^0[\oplus]$ via the Coin Problem
- Criticality of regular formulas
- Complexity of quantum circuits via sensitivity, magic, and coherence
- Harmonicity and invariance on slices of the Boolean cube
- Bounded-depth circuits cannot sample good codes
- Pseudorandom Functions: Three Decades Later
- Paradigms for Unconditional Pseudorandom Generators
- Separation results for Boolean function classes
- Expander-based cryptography meets natural proofs
- The influence of canalization on the robustness of Boolean networks
- On the minimum depth of circuits with linear number of wires encoding good codes
- Title not available (Why is that?)
- Learning $$AC^0$$ Under k-Dependent Distributions
- Noise sensitivity of Boolean functions and applications to percolation
- Pseudo-average block sensitivity equals average sensitivity
- Approximating Boolean Functions with Depth-2 Circuits
- On mappings on the hypercube with small average stretch
- Lipschitz bijections between boolean functions
- Homomorphic Evaluation Requires Depth
- Bounds on the Fourier coefficients of the weighted sum function
- Prediction from partial information and hindsight, with application to circuit lower bounds
- On the nonlinearity of the sequence of signs of Kloosterman sums
- The average sensitivity of bounded-depth formulas
- Ehrenfeucht-Fraïssé Games on Random Structures
- A note on the entropy/influence conjecture
- Bi-Lipschitz bijection between the Boolean cube and the Hamming ball
- On extremal \(k\)-CNF formulas
- Collectively canalizing Boolean functions
- Complexity measures and decision tree complexity: a survey.
- The Fourier Entropy–Influence Conjecture for Certain Classes of Boolean Functions
- Variable Influences in Conjunctive Normal Forms
- On extremal \(k\)-CNF formulas
- Boolean nested canalizing functions: a comprehensive analysis
- On the average sensitivity of the weighted sum function
- The simplified weighted sum function and its average sensitivity
- Quantum Talagrand, KKL and Friedgut's theorems and the learnability of quantum Boolean functions
This page was built for publication: The average sensitivity of bounded-depth circuits
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q290255)
