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 Read-Once Boolean Functions
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
Abstract
We survey some recent results on read-once Boolean functions. Among them are a characterization theorem, a generalization and a discussion on the randomized Boolean decision tree complexity for read-once functions. A previously unpublished result of Lovás and Newman is also presented.
Introduction
A Boolean formula is a rooted binary tree whose internal nodes are labeled by the Boolean operators ∨ or Λ and in which each leaf is labeled by a Boolean variable or its negation. A Boolean formula computes a Boolean function in a natural way.
A Boolean formula is read-once if every variable appears exactly once. A function is read-once if it has a read-once formula.
Read-once functions have been studied by many authors, since they have the lowest possible formula size (for functions that depend on all their variables). In addition, every NC1 function on n variables is a projection of a read-once function with a polynomial (in n) number of variables.
We present here some recent results in the area. All but one of those results have been published, hence, full proofs will be generally omitted and will be given just for the unpublished result (Theorem 3.4). The results we will discuss cover a characterization theorem, some generalizations and results on the randomized decision tree complexity of read-once functions. There is a recent result on learning of read-once functions, [AHK89], which will not be described.
Definitions and Notations
If g : {0, l}n ↦ {0, 1} has a formula in which no negated variable appears, we say that g is monotone. The size of a Boolean formula is the number of its leaves.
- Type
- Chapter
- Information
- Boolean Function Complexity , pp. 25 - 34Publisher: Cambridge University PressPrint publication year: 1992
- 3
- Cited by