Book contents
- Frontmatter
- Contents
- Preface
- List of Participants
- Relationships Between Monotone and Non-Monotone Network Complexity
- On Read-Once Boolean Functions
- Boolean Function Complexity: a Lattice-Theoretic Perspective
- Monotone Complexity
- On Submodular Complexity Measures
- Why is Boolean Complexity Theory so Difficult?
- The Multiplicative Complexity of Boolean Quadratic Forms, a Survey
- Some Problems Involving Razborov-Smolensky Polynomials
- Symmetry Functions in AC° can be Computed in Constant Depth with Very Small Size
- Boolean Complexity and Probabilistic Constructions
- Networks Computing Boolean Functions for Multiple Input Values
- Optimal Carry Save Networks
On Submodular Complexity Measures
Published online by Cambridge University Press: 23 September 2009
- Frontmatter
- Contents
- Preface
- List of Participants
- Relationships Between Monotone and Non-Monotone Network Complexity
- On Read-Once Boolean Functions
- Boolean Function Complexity: a Lattice-Theoretic Perspective
- Monotone Complexity
- On Submodular Complexity Measures
- Why is Boolean Complexity Theory so Difficult?
- The Multiplicative Complexity of Boolean Quadratic Forms, a Survey
- Some Problems Involving Razborov-Smolensky Polynomials
- Symmetry Functions in AC° can be Computed in Constant Depth with Very Small Size
- Boolean Complexity and Probabilistic Constructions
- Networks Computing Boolean Functions for Multiple Input Values
- Optimal Carry Save Networks
Summary
Introduction
In recent years several methods have been developed for obtaining superpolynomial lower bounds on the monotone formula and circuit size of explicitly given Boolean functions. Among these are the method of approximations, the combinatorial analysis of a communication problem related to monotone depth and the use of matrices with very particular rank properties. Now it can be said almost surely that each of these methods would need considerable strengthening to yield nontrivial lower bounds for the size of circuits or formulae over a complete basis. So, it seems interesting to try to understand from the formal point of view what kind of machinery we lack.
The first step in that direction was undertaken by the author in. In that paper two possible formalizations of the method of approximations were considered. The restrictive version forbids the method to use extra variables. This version was proven to be practically useless for circuits over a complete basis. If extra variables are allowed (the second formalization) then the method becomes universal, i.e. for any Boolean function f there exists an approximating model giving a lower bound for the circuit size of f which is tight up to a polynomial. Then the burden of proving lower bounds for the circuit size shifts to estimating from below the minimal number of covering sets in a particular instance of “MINIMUM COVER”. One application of an analogous model appears in where the first nonlinear lower bound was proven for the complexity of MAJORITY with respect to switching-and-rectifiers networks.
- Type
- Chapter
- Information
- Boolean Function Complexity , pp. 76 - 83Publisher: Cambridge University PressPrint publication year: 1992
- 14
- Cited by