Topological aspects of Boolean functions

DOI10.4310/PAMQ.2024.V20.N3.A1MaRDI QIDQ6400428zbMATH OpenFDO

Authors Anders Bjoerner, M. Goresky, Robert MacPherson

Publication date 28 May 2022

Mathematics Subject Classification ID

Combinatorics of partially ordered sets (06A07) Commutative rings defined by monomial ideals; Stanley-Reisner face rings; simplicial complexes (13F55) Circuits, networks (94Cxx) Miscellaneous topics in information and communication theory (94Dxx)

Abstract: We discuss ways in which tools from topology can be used to derive lower bounds for the circuit complexity of Boolean functions.

Recommendations

• Circuit complexity and multiplicative complexity of Boolean functions
• Complexity of Boolean functions over bases with unbounded fan-in gates
• On the complexity of realizing the powers of a Boolean \((n,n)\)-function
• Computational complexity of Boolean functions
• On the positive and the inversion complexity of Boolean functions

This page was built for publication: Topological aspects of Boolean functions

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