On the computational power of depth-2 circuits with threshold and modulo gates

DOI10.1016/S0304-3975(96)00019-9zbMath0908.68110MaRDI QIDQ1269909

Pavel Pudlák, Matthias Krause

Publication date: 22 October 1998

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

threshold-\(\text{MOD}^r\) circuitsthreshold-XOR circuits

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (20)

Hardness Amplification and the Approximate Degree of Constant-Depth Circuits ⋮ Breaking the Minsky--Papert Barrier for Constant-Depth Circuits ⋮ Nonuniform ACC Circuit Lower Bounds ⋮ The Power of Asymmetry in Constant-Depth Circuits ⋮ A small decrease in the degree of a polynomial with a given sign function can exponentially increase its weight and length ⋮ Upper and lower bounds for some depth-3 circuit classes ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Algorithmic Polynomials ⋮ The hardest halfspace ⋮ Optimal bounds for sign-representing the intersection of two halfspaces by polynomials ⋮ Exploring learnability between exact and PAC ⋮ Unnamed Item ⋮ Polynomial threshold functions and Boolean threshold circuits ⋮ Near-Optimal Lower Bounds on the Threshold Degree and Sign-Rank of AC$^0$ ⋮ Unconditional lower bounds for learning intersections of halfspaces ⋮ The Multiparty Communication Complexity of Set Disjointness ⋮ Depth Reduction for Circuits with a Single Layer of Modular Counting Gates ⋮ Unnamed Item ⋮ A Lifting Theorem with Applications to Symmetric Functions

Cites Work

• Unnamed Item
• Unnamed Item
• Non-uniform automata over groups
• A guided tour of Chernoff bounds
• Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
• Some notes on threshold circuits, and multiplication in depth 4
• Majority gates vs. general weighted threshold gates
• Exponential size lower bounds for some depth three circuits
• The expressive power of voting polynomials
• On the computational power of depth 2 circuits with threshold and modulo gates
• A weight-size trade-off for circuits with MOD m gates
• Harmonic Analysis of Polynomial Threshold Functions
• Simple Constructions of Almost k-wise Independent Random Variables
• Depth efficient neural networks for division and related problems
• Simulating threshold circuits by majority circuits

This page was built for publication: On the computational power of depth-2 circuits with threshold and modulo gates