scientific article

zbMATH Open0769.68051MaRDI QIDQ4036705FDOQ4036705

Sang-Zin Yi, Norbert Wurm, Ingo Wegener

Publication date: 18 May 1993

Title of this publication is not available (Why is that?)

Recommendations

• scientific article
• 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
• 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

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)

Cited In (7)

• Evaluating spectral norms for constant depth circuits with symmetric gates
• Title not available (Why is that?)
• Functions with bounded symmetric communication complexity, programs over commutative monoids, and ACC
• First-order expressibility of languages with neutral letters or: The Crane Beach conjecture
• Title not available (Why is that?)
• Bounded-depth, polynomial-size circuits for symmetric functions
• Computation of level-\(0\) kernels of symmetric logic functions

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)