Pure and Applied Mathematics Quarterly

Volume 20 (2024)

Number 3

Special Issue in Honor of Claudio Procesi

Guest Editors: Luca Migliorini, Paolo Papi, and Mario Salvetti

Topological aspects of Boolean functions

Pages: 1029 – 1063

DOI: https://dx.doi.org/10.4310/PAMQ.2024.v20.n3.a1

Authors

Anders Björner (Department of Mathematics, KTH Stockholm, Sweden)

Mark Goresky (School of Mathematics, Institute for Advanced Study, Princeton, New Jersey, U.S.A.)

Robert MacPherson (School of Mathematics, Institute for Advanced Study, Princeton, New Jersey, U.S.A.)

Abstract

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

Keywords

Boolean function, circuit complexity, order complex, Betti number, simplicial sheaf

2010 Mathematics Subject Classification

06A07, 13F55, 94Cxx, 94Dxx

Full Text (PDF format)

To Claudio Procesi, with friendship and admiration, on the occasion of his eightieth birthday

Received 2 June 2022

Received revised 14 November 2022

Accepted 3 January 2023

Published 15 May 2024