Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
type: Item
instance of: scholarly article
title: Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
zbMATH Open document ID: 0632.94030
DOI: 10.1007/BF01137685
published in: Mathematical Notes
publication date: 1987-01-01T00:00:00Z
review text: Lower bounds for bounded depth circuits over \(\{\) \&,\(\vee,\oplus \}\) are given using a special structure of families of Boolean functions called regular models. The construction of bounded degree is described. These models are then used to deduce exponential lower bounds in the basis \(\{\) \&,\(\oplus \}\), and it is shown that they also hold in the basis \(\{\) \&,\(\vee,\oplus \}\).
Mathematics Subject Classification ID: 94C10
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 4029460
zbMATH Keywords: circuit complexity of Boolean functions
zbMATH Keywords: bounded depth circuits
zbMATH Keywords: regular models
zbMATH Keywords: exponential lower bounds
author: Alexander Razborov
reviewed by: Leon Livovschi
MaRDI profile type: Publication
Wikidata QID: Q29042011
cites work: A Boolean function requiring 3n network size
cites work: Parity, circuits, and the polynomial-time hierarchy
cites work: \(\Sigma_ 1^ 1\)-formulae on finite structures
cites work: Q3758729
cites work: Q4726174
cites work: The monotone circuit complexity of Boolean functions
cites work: Q4724549
full work available at URL: https://doi.org/10.1007/bf01137685
OpenAlex ID: W2009994177
description: scientific article; zbMATH DE number 4029460