Optimal depth, very small size circuits for symmetric functions in \(AC^ 0\)
From MaRDI portal
Publication:1322486
DOI10.1006/inco.1994.1008zbMath0794.68060OpenAlexW2125763748WikidataQ56959128 ScholiaQ56959128MaRDI QIDQ1322486
Ingo Wegener, Sang-Zin Yi, Norbert Wurm, Johan T. Håstad
Publication date: 31 August 1994
Published in: Information and Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1006/inco.1994.1008
symmetric Boolean functionsBoolean complexitycomplexity class \(AC^ 0\)massive parallel unbounded fan-in circuitsoptimal depth
Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).
Related Items (6)
Uniform constant-depth threshold circuits for division and iterated multiplication. ⋮ Coloring k-colorable graphs in constant expected parallel time ⋮ Identification of partial disjunction, parity, and threshold functions ⋮ On the $AC^0$ Complexity of Subgraph Isomorphism ⋮ Beating treewidth for average-case subgraph isomorphism ⋮ Attribute-efficient learning in query and mistake-bound models
This page was built for publication: Optimal depth, very small size circuits for symmetric functions in \(AC^ 0\)
