The complexity of the parity function in unbounded fan-in, unbounded depth circuits
From MaRDI portal
Publication:1183575
DOI10.1016/0304-3975(91)90052-4zbMath0749.94025MaRDI QIDQ1183575
Publication date: 28 June 1992
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0304-3975(91)90052-4
complexity measure; Boolean function complexity theory; complexity of the parity function; unbounded fan-in Boolean circuits
68Q25: Analysis of algorithms and problem complexity
Related Items
Upper estimate of realization complexity of linear functions in a basis consisting of multi-input elements, Size-energy tradeoffs for unate circuits computing symmetric Boolean functions, Some notes on threshold circuits, and multiplication in depth 4, On the complexity of encoding in analog circuits, Complexity and structure of circuits for parity functions, Lower bound of circuit complexity of parity function in a basis of unbounded fan-in, On the positive and the inversion complexity of Boolean functions
Cites Work