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.