A lower bound for depth-3 circuits with MOD \(m\) gates

DOI10.1016/S0020-0190(98)00093-3zbMath1338.68106OpenAlexW2039809882MaRDI QIDQ293324

Vince Grolmusz

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

zbMATH Keywords

computational complexitycircuit complexityrandomized algorithmscommunication complexitycomplexity of finite functioncomposite moduli

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20)

Related Items

Nonuniform ACC Circuit Lower Bounds, Unnamed Item

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