Majority gates vs. general weighted threshold gates
From MaRDI portal
Publication:1210330
DOI10.1007/BF01200426zbMath0770.68054OpenAlexW2097886040WikidataQ56959157 ScholiaQ56959157MaRDI QIDQ1210330
Mikael Goldmann, Johan T. Håstad, Alexander A. Razborov
Publication date: 8 August 1993
Published in: Computational Complexity (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf01200426
Related Items
Biased halfspaces, noise sensitivity, and local Chernoff inequalities, Monotone Boolean formulas can approximate monotone linear threshold functions, \(n^{{\Omega{}}(\log{} n)}\) lower bounds on the size of depth-3 threshold circuits with AND gates at the bottom, On the power of a threshold gate at the top, A lower bound for depth-3 circuits with MOD \(m\) gates, Local Reductions, Learning DNF in time \(2^{\widetilde O(n^{1/3})}\), On small depth threshold circuits, Powering requires threshold depth 3, Local reduction, Lower bounds for one-way probabilistic communication complexity and their application to space complexity, Breaking the Minsky--Papert Barrier for Constant-Depth Circuits, Evaluating spectral norms for constant depth circuits with symmetric gates, General-Purpose Computation with Neural Networks: A Survey of Complexity Theoretic Results, Geometric arguments yield better bounds for threshold circuits and distributed computing, A new central limit theorem and decomposition for Gaussian polynomials, with an application to deterministic approximate counting, Strong Average-Case Circuit Lower Bounds from Nontrivial Derandomization, A small decrease in the degree of a polynomial with a given sign function can exponentially increase its weight and length, A Short List of Equalities Induces Large Sign-Rank, An efficient membership-query algorithm for learning DNF with respect to the uniform distribution, Decomposition of threshold functions into bounded fan-in threshold functions, Neural networks and complexity theory, On the power of circuits with gates of low \(L_{1}\) norms., Linear threshold functions in decision lists, decision trees, and depth-2 circuits, Exponential lower bound for bounded depth circuits with few threshold gates, The unbounded-error communication complexity of symmetric functions, Monomial Boolean functions with large high-order nonlinearities, Unnamed Item, Unnamed Item, Complexity of hard-core set proofs, A note on the power of majority gates and modular gates, The communication complexity of addition, Threshold circuit lower bounds on cryptographic functions, On XOR lemmas for the weight of polynomial threshold functions, Polynomial threshold functions and Boolean threshold circuits, Cryptographic hardness for learning intersections of halfspaces, Optimal lower bounds on the depth of polynomial-size threshold circuits for some arithmetic functions, Quantum matchgate computations and linear threshold gates, On Functions Computed on Trees, Correlation Bounds for Poly-size $\mbox{\rm AC}^0$ Circuits with n 1 − o(1) Symmetric Gates, On the computational power of depth-2 circuits with threshold and modulo gates, Threshold circuits of small majority-depth, Stronger connections between circuit analysis and circuit lower bounds, via PCPs of proximity, Bounded depth circuits with weighted symmetric gates: satisfiability, lower bounds and compression, Unnamed Item, Unnamed Item, Computing majority by constant depth majority circuits with low fan-in gates, Can large fanin circuits perform reliable computations in the presence of faults?, Quantum Hardness of Learning Shallow Classical Circuits, Monotone circuits for monotone weighted threshold functions, On weak base hypotheses and their implications for boosting regression and classification, Unnamed Item, Efficient threshold circuits for power series, A Lifting Theorem with Applications to Symmetric Functions, A \#SAT algorithm for small constant-depth circuits with PTF gates
Cites Work
