Bounded-depth, polynomial-size circuits for symmetric functions (Q1063574): Difference between revisions
From MaRDI portal
Set OpenAlex properties. |
ReferenceBot (talk | contribs) Changed an Item |
||
Property / cites work | |||
Property / cites work: \(\Sigma_ 1^ 1\)-formulae on finite structures / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Constant Depth Reducibility / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5606602 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3290963 / rank | |||
Normal rank |
Latest revision as of 19:00, 14 June 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Bounded-depth, polynomial-size circuits for symmetric functions |
scientific article |
Statements
Bounded-depth, polynomial-size circuits for symmetric functions (English)
0 references
1985
0 references
Let \(\{f_ 1,f_ 2,...\}\) be a family of symmetric Boolean functions, where \(f_ n\) has n variables. For this family the minimum number of variables of \(f_ n\) is considered that have to be set to constant values so that the resulting function is a constant function. It is shown that the growth rate of this minimum completely determines whether or not the given family if ''good'', that is, can be realized by a family of constant-depth, polynomial-size circuits (with unbounded fan-in), and explicit growth rates, which define good respectively bad families, are given. The authors' results provide a unifying framework to show why the families of parity and majority functions are bad. (From the text).
0 references
spectrum
0 references
measure function
0 references
parity functions
0 references
symmetric Boolean functions
0 references
growth rate
0 references
majority functions
0 references