Search

In this chapter we will discuss two central results of complexity theory that we know something about, thanks to the foundational work of Patrick Fischer. Yet these results have not been improved for decades, and perhaps now is the time, finally, to make some progress on them.

In the 2nd Annual FOCS (1961), C. K. Chow proved that every Boolean threshold function is uniquely determined by its degree-0 and degree-1 Fourier coefficients. These numbers became known as the Chow Parameters. Providing an algorithmic version of Chow's theorem --- i.e., efficiently constructing a representation of a threshold function given its Chow Parameters --- has remained open ever since. This problem has received significant study in the fields of circuit complexity, game theory and the design of voting systems, and learning theory. In this paper we effectively solve the problem, giving a randomized PTAS with the following behavior: Theorem: Given the Chow Parameters of a Boolean threshold function f over n bits and any constant e > 0, the algorithm runs in time O(n2 log2 n) and with high probability outputs a representation of a threshold function f' which is e-close to f. Along the way we prove several new results of independent interest about Boolean threshold functions. In addition to various structural results, these include the following new algorithmic results in learning theory (where threshold functions are usually called "halfspaces"): An ~O(n2)-time uniform distribution algorithm for learning halfspaces to constant accuracy in the "Restricted Focus of Attention" (RFA) model of Ben-David et al. [3]. This answers the main open question of [6]. An O(n2)-time agnostic-type learning algorithm for halfspaces under the uniform distribution. This contrasts with recent results of Guruswami and Raghavendra [21] who show that the learning problem we solve is NP-hard under general distributions. As a special case of the latter result we obtain the fastest known algorithm for learning halfspaces to constant accuracy in the uniform distribution PAC learning model. For constant e our algorithm runs in time ~O(n2), which substantially improves on previous bounds and nearly matches the Ω(n2) bits of training data that any successful learning algorithm must use.

This paper presents a technique to determine prime implicants in multi-level combinational networks. The method is based on a graph representation of Boolean functions called AND/OR reasoning graphs. This representation follows from a search strategy to solve the satisfiability problem that is radically different from conventional search for this purpose (such as exhaustive simulation, backtracking, BDDs). The paper shows how to build AND/OR reasoning graphs for arbitrary combinational circuits and proves basic theoretical properties of the graphs. It will be demonstrated that AND/OR reasoning graphs allow us to naturally extend basic notions of two-level switching circuit theory to multi-level circuits. In particular, the notions of prime implicants and permissible prime implicants are defined for multi-level circuits and it is proved that AND/OR reasoning graphs represent all these implicants. Experimental results are shown for PLA factorization.

Immunological control networks can be modelled by bipartite signed directed graphs called influence diagrams. Possible flow topologies around unstable steady states in such systems can be determined by kinetic logic based on the directed Boolean cubes of switching circuit theory. This method can identify the stable ''help'' and ''suppression'' configurations of the basic Herzenberg core regulatory circuit as well as the ''memory'' and ''non-responsive'' configurations of the model of Kaufman, Urbain and Thomas. Furthermore, addition of a single vertex to the Herzenberg core regulatory circuit, so as to preserve the bipartite nature of the signed directed graph, leads to a network with five independent internal variables and two connected feedback circuits, either positive and negative circuits of length 4 or positive circuits of lengths 4 and 2. The flow topology of either of these systems indicates that addition of the fifth vertex switches the basic four-vertex core regulatory circuit into one of its two stable configurations.

A method of analysis of relations between performance and patterns of decision criteria for a test battery (pass-fail) using Boolean switching circuit theory is presented. The method does not require assumptions of additivity, linearity or independence, usually required by profile and/or regression methods and deals equally well with nominal as well as scaled data.

Presented in this correspondence is a tabular method for obtaining minimal sum-of-products representations of Boolean functions. The method uses a single table called the adjacency table. This table provides a record of the adjacency properties of the minterms of the given function. In particular, the table records 1) all adjacent pairs of minterms, 2) the variable absent from each product term subsumed by each pair of adjacent minterms, and 3) each minterm that is adjacent to no minterm. From this table, prime implicants of the function are readily determined by using a simple set operation-intersection-on the sets of absent variables.

This paper developes two algorithms for finding the time-dependent reliability of any active-redundant system in terms of component failure probabilities. These algorithms apply to non-loaded, continuously-operating systems in which drift-type failures are neglected. The first algorithm is used when each component can fail in only one mode. A procedure, based on the Quine-McCluskey technique from switching circuit theory, is stated in conjunction with this algorithm which permits rapid simplification of the reliability expression. Two failure modes are permitted in the second algorithm. The relation between the expressions resulting from the algorithms and lifetime random variables is given so that the algorithms do not depend on specific component failure distributions.

This paper combines the compensation of control systems with transient analysis and switching circuit theory to accomplish the discrete compensation of control systems. Several transfer functions are used as examples, and their realizations are discussed in detail. Lead and lag compensation are used, and several general transfer function realizations are presented for clarity. All of the realizations have been implemented with methods suitable for complete circuit integration, i.e., the logic circuits required for implementation are all commonly available in large quantities on a single integrated circuit chip.

Symmetric circuits with more than one output can traditionally be reduced by shifting down if the outputs have certain properties. It is shown here that any nontrivial symmetric circuit can be shifted down using the method described. The reduction is made logical and simple to understand by means of the concept of logical potential, in which the circuit is diagrammed, and a "potential" assigned to each node in the diagram. The method shows which shifts are valid and avoids those which result in sneak circuits. It provides an excellent tutorial approach for classroom teaching of symmetric circuit reduction in courses on logic and switching circuit theory.

Theory of computing means the abstract study of the nature of computation and computing devices. By convention, the terminology is usually applied in a narrower sense to exclude numerical analysis. Thus, theory of computing includes the theory of finite automata, formal languages, computability, computational complexity, and some aspects of switching circuit theory and logical design. The deviation from the literal meaning of the term may have occurred because numerical analysis was already a well-established subject when the other components of this area were in their infancy. On the other hand, it may be a reflection of the emphasis on discrete mathematics by workers in theory of computing, in contrast to the preponderance of continuous methods in numerical analysis.