In this dissertation we explore a central theme of the theory of computing: the study of the inherent complexity of computational tasks via combinatorial models such as Boolean circuits, span programs, branching programs.
In the first part of the thesis we study fault tolerance of Boolean circuits.
First we study the model of independent random faults, introduced by von Neumann. In this model the gates of the circuit may fail with a probability bounded by some small constant, and the failures occur independently. A circuit is reliable, if it produces the correct result with high probability on any input. We give a general lower bound for the size needed for the reliable computation of Boolean functions in this model. In some cases this matches the known upper bounds. We prove that the reliable computation of any Boolean function with sensitivity s requires \Omega(s \log s) gates if the gates of the circuit fail independently with a fixed positive probability. This theorem was stated by Dobrushin and Ortyukov in 1977, but their proof was not complete as pointed out by Pippenger, Stamoulis and Tsitsiklis in 1991. We use the general approach of Dobrushin and Ortyukov together with a new probabilistic argument. The \Omega(s \log s) bound holds even if s is the block sensitivity instead of the sensitivity of the Boolean function.
Next we introduce a model for adversarial faults. We consider synchronized circuits and we allow an adversary to choose a small constant fraction of the gates at each level of the circuit to be faulty. We require that even in the presence of such faults the circuit compute a ``loose version'' of the given function. We present an efficient construction for computing arbitrary symmetric functions in this model. We also show a perhaps unexpected relation between this model and probabilistically checkable proofs.
The second part of the thesis gives two lower bounds for computing Boolean functions. The first result provides lower bounds for monotone span programs, a model introduced in 1993 by Karchmer and Wigderson. The second result exhibits an AC^0-computable function that requires exponential size read-once branching programs. Both lower bounds are based on combinatorial properties of the families of minterms of the functions computed.
In the third part of the thesis we study the relation of Boolean and arithmetic circuits. We prove that polynomial size semi-unbounded fan-in Boolean circuits of depth d with n inputs can be simulated by polynomial size semi-unbounded fan-in arithmetic circuits of depth O(d+ \log n), where the arithmetic operations +, -, x, are performed in an arbitrary finite field. The proof is based on a randomized reduction using the Isolation Lemma of Mulmuley, Vazirani and Vazirani.
Table of contents:
