Daniel J. Kleitman

FOCS Conference 1994 Conference Paper

On the Design of Reliable Boolean Circuits that Contain Partially Unreliable Gates

• Daniel J. Kleitman
• Frank Thomson Leighton
• Yuan Ma

We investigate a model of gate failure for Boolean circuits in which a faulty gate is restricted to output one of its input values. For some types of gates, the model (which we call the short-circuit model of gate failure) is weaker than the traditional von Neumann model where faulty gates always output precisely the wrong value. Our model has the advantage that it allows us to design Boolean circuits that can tolerate worst-case faults, as well as circuits that have arbitrarily high success probability in the case of random faults. Moreover, the short-circuit model captures a particular type of fault that commonly appears in practice, and it suggests a simple method for performing post-test alterations to circuits that have more severe types of faults. A variety of bounds on the size of fault-tolerant circuits are proved in the paper. Perhaps, the most important is a proof that any k-fault-tolerant circuit for any input-sensitive function using any type of gates (even arbitrarily powerful, multiple-input gates) must have size at least /spl Omega/(k log k/log log k). Obtaining a tight bound on the size of a circuit for computing the AND of two values if up to k of the gates are faulty is one of the central questions left open in the paper. >

STOC Conference 1984 Conference Paper

An Algorithm for Constructing Regions with Rectangles: Independence and Minimum Generating Sets for Collections of Intervals

• Deborah S. Franzblau
• Daniel J. Kleitman

TCS Journal 1981 Journal Article

Inherent complexity trade-offs for range query problems

• Walter A. Burkhard
• Michael L. Fredman
• Daniel J. Kleitman

STOC Conference 1981 Conference Paper

New Layouts for the Shuffle-Exchange Graph (Extended Abstract)

• Daniel J. Kleitman
• Frank Thomson Leighton
• Margaret Lepley
• Gary L. Miller

STOC Conference 1978 Conference Paper

Coping with Errors in Binary Search Procedures (Preliminary Report)

• Ronald L. Rivest
• Albert R. Meyer
• Daniel J. Kleitman
• Karl Winklmann
• Joel Spencer

We consider the problem of identifying an unknown value xε{1,2,...,n} using only comparisons of x to constants when as many as E of 'the comparisons may receive erroneous answers. For a continuous analogue of this problem we show that there is a unique strategy that is optimal in the worst case. This strategy for the continuous problem is then shown to yield a strategy for the original discrete problem that uses log 2 n+E.log 2 log 2 n+O(E.log 2 E) comparisons in the worst case. This number is shown to be optimal even if arbitrary “Yes-No” questions are allowed. We show that a modified version of this search problem with errors is equivalent to the problem of finding the minimal root of a set of increasing functions. The modified version is then also shown to be of complexity log 2 n+E.log 2 log 2 n+0(E.log 2 E).

FOCS Conference 1975 Conference Paper

An Optimal Bound for Two Dimensional Bin Packing

• Daniel J. Kleitman
• Michael M. Krieger

Bin packing and dynamic allocation problems hold an important place both in theoretical computer science and in practical issues arising in computer applications and operations research. While major analytic advances have been made for the 1-dimension case, optimal results for 2-dimensional problems have been elusive. As a model for analysis of various multidimensional bin packing and cutting stock problems, we consider the following question. Let be an arbitrary finite family of squares of total area at most unity; what is the smallest rectangle into which any such family can be packed without overlap? We answer this with the following optimal result: 1) any unit family can be packed into a rectangle with sides 2/√3 and √2; 2) any other rectangle with this packing property has larger area. The proof of this is rather lengthy and technical. We therefore restrict this presentation to a general discussion of the methods used and an outline of the major cases together with some specific examples.