Circuits constructed with MOD\(_ q\) gates cannot compute ``and in sublinear size

DOI10.1007/BF01263425zbMath0829.68048OpenAlexW1582780661MaRDI QIDQ1346618

Denis Thérien

Publication date: 6 April 1995

Published in: Computational Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01263425

zbMATH Keywords

algebraic techniquesbounded-depth circuitsboolean functions

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30)

Related Items (3)

Upper and lower bounds for some depth-3 circuit classes ⋮ Dual VP classes ⋮ A topological approach to non-uniform complexity

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
• On mod \(p\) transversals
• Parity, circuits, and the polynomial-time hierarchy

This page was built for publication: Circuits constructed with MOD\(_ q\) gates cannot compute ``and in sublinear size