scientific article; zbMATH DE number 176874

MaRDI QIDQ4036705zbMATHFDO

Authors Ingo Wegener, Norbert Wurm, Sang-Zin Yi

Publication date 18 May 1993

zbMATH Keywords

symmetric Boolean functionscomplexity class \(AC^ 0\)unbounded fan-in circuits

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• scientific article; zbMATH DE number 4209604
• Optimal depth, very small size circuits for symmetric functions in \(AC^ 0\)
• Bounded-depth, polynomial-size circuits for symmetric functions
• The complexity of symmetric functions in bounded-depth circuits
• scientific article; zbMATH DE number 165425
• scientific article; zbMATH DE number 1222830
• Concrete Multiplicative Complexity of Symmetric Functions
• An exact characterization of symmetric functions in \(qAC^{0}[2]\)
• Tight bounds for the multiplicative complexity of symmetric functions
• On complexity of realisation of a class of almost symmetric functions by formulas of depth 3

Cited in

(9)

• On the power of small-depth computation
• Subspace-invariant \(\mathrm{AC}^0\) formulas
• Bounded-depth, polynomial-size circuits for symmetric functions
• First-order expressibility of languages with neutral letters or: The Crane Beach conjecture
• Computation of level-\(0\) kernels of symmetric logic functions
• Functions with bounded symmetric communication complexity, programs over commutative monoids, and ACC
• Evaluating spectral norms for constant depth circuits with symmetric gates
• scientific article; zbMATH DE number 89639 (Why is no real title available?)
• scientific article; zbMATH DE number 4209604 (Why is no real title available?)

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4036705)