The average sensitivity of bounded-depth circuits
From MaRDI portal
Recommendations
Cites work
- scientific article; zbMATH DE number 1142303 (Why is no real title available?)
- Constant depth circuits, Fourier transform, and learnability
- Limiting Negations in Constant Depth Circuits
- Method of determining lower bounds for the complexity of \(\Pi\)-circuits
- Parity, circuits, and the polynomial-time hierarchy
- The computational complexity of universal hashing
- \(\Sigma_ 1^ 1\)-formulae on finite structures
Cited in
(40)- On the minimum depth of circuits with linear number of wires encoding good codes
- Ehrenfeucht-Fraïssé Games on Random Structures
- Paradigms for Unconditional Pseudorandom Generators
- Expander-based cryptography meets natural proofs
- On mappings on the hypercube with small average stretch
- Complexity of quantum circuits via sensitivity, magic, and coherence
- Lipschitz bijections between boolean functions
- Robust topology optimization for periodic structures by combining sensitivity averaging with a semianalytical method
- Separation results for Boolean function classes
- Approximating Boolean functions with depth-2 circuits
- The influence of canalization on the robustness of Boolean networks
- Collectively canalizing Boolean functions
- The average sensitivity of bounded-depth formulas
- Prediction from partial information and hindsight, with application to circuit lower bounds
- On extremal \(k\)-CNF formulas
- Circuit and decision tree complexity of some number theoretic problems
- Learning \(\mathrm{AC}^0\) under \(k\)-dependent distributions
- Boolean nested canalizing functions: a comprehensive analysis
- A Fixed-Depth Size-Hierarchy Theorem for $\mathrm{AC}^0[\oplus]$ via the Coin Problem
- The Fourier entropy-influence conjecture for certain classes of Boolean functions
- Bi-Lipschitz bijection between the Boolean cube and the Hamming ball
- Variable Influences in Conjunctive Normal Forms
- Bounds on the Fourier coefficients of the weighted sum function
- Bounded-depth circuits cannot sample good codes
- Pseudorandom functions: three decades later
- scientific article; zbMATH DE number 7250165 (Why is no real title available?)
- On the nonlinearity of the sequence of signs of Kloosterman sums
- A note on the entropy/influence conjecture
- Quantum Talagrand, KKL and Friedgut's theorems and the learnability of quantum Boolean functions
- An average-case depth hierarchy theorem for Boolean circuits
- On the average sensitivity of the weighted sum function
- Tight bounds on the average sensitivity of k-CNF
- Noise sensitivity of Boolean functions and applications to percolation
- Complexity measures and decision tree complexity: a survey.
- Pseudo-average block sensitivity equals average sensitivity
- Harmonicity and invariance on slices of the Boolean cube
- Homomorphic evaluation requires depth
- The simplified weighted sum function and its average sensitivity
- Criticality of regular formulas
- On extremal \(k\)-CNF formulas
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)
