The complexity of symmetric functions in bounded-depth circuits

DOI10.1016/0020-0190(87)90163-3MaRDI QIDQ1107989zbMATH OpenOpenAlexFDO

Authors Bettina Brustmann, Ingo Wegener

Publication date 1987

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0020-0190(87)90163-3

zbMATH Keywords

bounded-depth circuitcombinatorial complexity measuresensitive complexitysymmetric functions

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Cites work

• Bounded-depth, polynomial-size circuits for symmetric functions
• Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
• Parity, circuits, and the polynomial-time hierarchy
• Properties of complexity measures for PRAMs and WRAMs

Cited in

(10)

• Entropy of contact circuits and lower bounds on their complexity
• The complexity of computing symmetric functions using threshold circuits
• Bit complexity of breaking and achieving symmetry in chains and rings (extended abstract)
• scientific article; zbMATH DE number 4209604 (Why is no real title available?)
• scientific article; zbMATH DE number 176874 (Why is no real title available?)
• On the Probabilistic Degrees of Symmetric Boolean Functions
• An exact characterization of symmetric functions in \(qAC^{0}[2]\)
• Coloring k-colorable graphs in constant expected parallel time
• Violating constant degree hypothesis requires breaking symmetry
• Tight bounds for the multiplicative complexity of symmetric functions

This page was built for publication: The complexity of symmetric functions in bounded-depth circuits

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