A lower bound for depth-3 circuits with MOD \(m\) gates
From MaRDI portal
Publication:293324
DOI10.1016/S0020-0190(98)00093-3zbMath1338.68106OpenAlexW2039809882MaRDI QIDQ293324
Publication date: 9 June 2016
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: http://www.sciencedirect.com/science/article/pii/S0020019098000933?np=y
computational complexitycircuit complexityrandomized algorithmscommunication complexitycomplexity of finite functioncomposite moduli
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Non-uniform automata over groups
- \(\Sigma_ 1^ 1\)-formulae on finite structures
- Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
- Majority gates vs. general weighted threshold gates
- Representing Boolean functions as polynomials modulo composite numbers
- A note on a theorem of Barrington, Straubing and Thérien
- Threshold circuits of bounded depth
- Parity, circuits, and the polynomial-time hierarchy
- Unbiased Bits from Sources of Weak Randomness and Probabilistic Communication Complexity