Circuits constructed with MOD\(_ q\) gates cannot compute ``and'' in sublinear size
type: Item
instance of: scholarly article
title: Circuits constructed with MOD\(_ q\) gates cannot compute ``and'' in sublinear size
zbMATH Open document ID: 0829.68048
DOI: 10.1007/BF01263425
author: Denis Thérien
published in: Computational Complexity
publication date: 1995-04-06T00:00:00Z
Mathematics Subject Classification ID: 68Q05
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68W30
zbMATH DE Number: 741034
zbMATH Keywords: algebraic techniques
zbMATH Keywords: bounded-depth circuits
zbMATH Keywords: boolean functions
MaRDI profile type: Publication
cites work: \(\Sigma_ 1^ 1\)-formulae on finite structures
cites work: Q4036704
cites work: Non-uniform automata over groups
cites work: Parity, circuits, and the polynomial-time hierarchy
cites work: Q3775466
cites work: On mod \(p\) transversals
cites work: Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
full work available at URL: https://doi.org/10.1007/bf01263425
OpenAlex ID: W1582780661
Recommended article: A weight-size trade-off for circuits with MOD \(m\) gates
Recommended article: Automata, Languages and Programming
Recommended article: Quantum circuits for \(\mathbb F_{2^n}\)-multiplication with subquadratic gate count
Recommended article: Gate elimination: circuit size lower bounds and \#SAT upper bounds
Recommended article: Q5368903
Recommended article: Q4601837
Recommended article: A lower bound for depth-3 circuits with MOD \(m\) gates
Recommended article: Lower bounds for modular counting by circuits with modular gates
Recommended article: Towards an Almost Quadratic Lower Bound on the Monotone Circuit Complexity of the Boolean Convolution
description: scientific article; zbMATH DE number 741034