Synopses & Reviews
Here Professor Paterson brings together papers from the 1990 Durham symposium on Boolean function complexity. The participants include many well known figures in the field.
Synopsis
Papers from the 1990 Durham symposium on Boolean function complexity reveal exciting advances over recent years in a long established area of discrete mathematics that uses combinatorial and occasionally algebraic methods.
Table of Contents
1. Relationships between monotone and non-monotone network complexity; 2. On read-once Boolean functions; 3. Boolean function complexity: a lattice-theoretic perspective; 4. Monotone complexity; 5. On submodular complexity measures; 6. Why is Boolean complexity so difficult?; 7. The multiplicative complexity of Boolean quadratic forms; 8. Some problems involving Razborov-Smolensky polynomials; 9. Symmetry functions in AC0; 10. Boolean complexity and probabilistic constructions; 11. Networks computing Boolean functions for multiple input values; 12. Optimal carry save networks.