Majority gates vs. general weighted threshold gates
From MaRDI portal
(Redirected from Publication:1210330)
Recommendations
Cites work
- Harmonic Analysis of Polynomial Threshold Functions
- scientific article; zbMATH DE number 4033058 (Why is no real title available?)
- scientific article; zbMATH DE number 3385535 (Why is no real title available?)
- On the Power of Threshold Circuits with Small Weights
- Polynomial Threshold Functions, AC^0 Functions, and Spectral Norms
Cited in
(64)- Monotone circuits for monotone weighted threshold functions
- On the computational power of depth-2 circuits with threshold and modulo gates
- Threshold circuits of small majority-depth
- When do extra majority gates help? Polylog\((N)\) majority gates are equivalent to one
- Lower bounds for one-way probabilistic communication complexity and their application to space complexity
- Geometric arguments yield better bounds for threshold circuits and distributed computing
- An efficient membership-query algorithm for learning DNF with respect to the uniform distribution
- On the power of circuits with gates of low \(L_{1}\) norms.
- Can large fanin circuits perform reliable computations in the presence of faults?
- Local reduction
- A new central limit theorem and decomposition for Gaussian polynomials, with an application to deterministic approximate counting
- Optimal lower bounds on the depth of polynomial-size threshold circuits for some arithmetic functions
- On weak base hypotheses and their implications for boosting regression and classification
- Efficient threshold circuits for power series
- Monotone Boolean formulas can approximate monotone linear threshold functions
- Learning DNF in time \(2^{\widetilde O(n^{1/3})}\)
- Evaluating spectral norms for constant depth circuits with symmetric gates
- A \#SAT algorithm for small constant-depth circuits with PTF gates
- On XOR lemmas for the weight of polynomial threshold functions
- Bounded depth circuits with weighted symmetric gates: satisfiability, lower bounds and compression
- Computing majority by constant depth majority circuits with low fan-in gates
- \(n^{{\Omega{}}(\log{} n)}\) lower bounds on the size of depth-3 threshold circuits with AND gates at the bottom
- The unbounded-error communication complexity of symmetric functions
- Threshold circuit lower bounds on cryptographic functions
- Polynomial threshold functions and Boolean threshold circuits
- Cryptographic hardness for learning intersections of halfspaces
- Impossibility results for weak threshold networks
- On the power of a threshold gate at the top
- A lower bound for depth-3 circuits with MOD m gates
- Quantum matchgate computations and linear threshold gates
- Correlation bounds for poly-size \(\mathrm{AC}^0\) circuits with \(n^{1 - o(1)}\) symmetric gates
- Local reductions
- A small decrease in the degree of a polynomial with a given sign function can exponentially increase its weight and length
- Decomposition of threshold functions into bounded fan-in threshold functions
- On the Power of Threshold Circuits with Small Weights
- Exponential lower bound for bounded depth circuits with few threshold gates
- Simulating Threshold Circuits by Majority Circuits
- Complexity of hard-core set proofs
- Breaking the Minsky--Papert Barrier for Constant-Depth Circuits
- Separation of unbounded-error models in multi-party communication complexity
- On multiparty communication with large versus unbounded error
- General-Purpose Computation with Neural Networks: A Survey of Complexity Theoretic Results
- Quantum hardness of learning shallow classical circuits
- Approximate degree and the complexity of depth three circuits
- Satisfiability and derandomization for small polynomial threshold circuits
- On small depth threshold circuits
- Strong Average-Case Circuit Lower Bounds from Nontrivial Derandomization
- A short list of equalities induces large sign-rank
- Stronger connections between circuit analysis and circuit lower bounds, via PCPs of proximity
- Neural networks and complexity theory
- A lifting theorem with applications to symmetric functions
- The large-error approximate degree of \(\mathrm{AC}^0\)
- The communication complexity of addition
- Biased halfspaces, noise sensitivity, and local Chernoff inequalities
- On functions computed on trees
- Linear threshold functions in decision lists, decision trees, and depth-2 circuits
- A note on the simulation of exponential threshold weights
- Monomial Boolean functions with large high-order nonlinearities
- A strongly polynomial algorithm for approximate Forster transforms and its application to halfspace learning
- Circuit complexity before the dawn of the new millennium
- A note on the power of majority gates and modular gates
- Bit-security preserving hardness amplification
- Majority vs. approximate linear sum and average-case complexity below NC^1
- Powering requires threshold depth 3
This page was built for publication: Majority gates vs. general weighted threshold gates
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1210330)
