Limiting negations in non-deterministic circuits

The minimum number of NOT gates in a Boolean circuit computing a Boolean function f is called the inversion complexity of f. In 1958, Markov determined the inversion complexity of every Boolean function and, in particular, proved that log₂(n+1) NOT gates are sufficient to compute any Boolean function on n variables. In this paper, we consider circuits computing non-deterministically and determine the inversion complexity of every Boolean function. In particular, we prove that one NOT gate is sufficient to compute any Boolean function in non-deterministic circuits if we can use an arbitrary number of guess inputs.     

Malign Distributions for Average Case Circuit Complexity

In contrast to machine models like Turing machines or random access machines, circuits are a static computational model. The internal information flow of a computation is fixed in advance, independent of the actual input. Therefore, size and depth are natural and simple measures for circuits and provide a worst-case analysis. We consider a new model in which an internal gate is evaluated as soon as its result has been determined by a partial assignment of its inputs. This way, a dynamic notion of delay is obtained which gives rise to an average case measure for the time complexity of circuits. In a previous paper we have obtained tight upper and lower bounds for the average case complexity of several basic Boolean functions. This paper examines the asymptotic average case complexity for the set of alln-ary Boolean functions. In contrast to worst case analysis a simple counting argument does not work. We prove that with respect to the uniform probability distribution almost all Boolean functions require at leastn−log n−log log nexpected time. On the other hand, there is a significantly large subset of functions that can be computed with a constant average delay. Finally, for an arbitrary Boolean function we compare its worst case and average case complexity. It is shown that for each function that requires circuit depthd, i.e. of worst-case complexityd, the expected time complexity will be at leastd−log n−log dwith respect to an explicitly defined probability distribution. In addition, a nontrivial upper bound on the complexity of such a distribution will be obtained.     

Verification of arithmetic circuits using binary moment diagrams

Binary moment diagrams (BMDs) provide a canonical representation for linear functions similar to the way binary decision diagrams (BDDs) represent Boolean functions. Within the class of linear functions, we can embed arbitrary functions from Boolean variables to real, rational, or integer values. BMDs can thus model the functionality of data path circuits operating over word-level data. Many important functions, including integer multiplication, that cannot be represented efficiently at the bit level with BDDs, have simple representations at the word level with BMDs. Furthermore, BMDs can represent Boolean functions as a special case. We propose a hierarchical approach to verifying arithmetic circuits, where component modules are first shown to implement their word-level specifications. The overall circuit functionality is then verified by composing the component functions and comparing the result to the word-level circuit specification. Multipliers with word sizes of up to 256 bits have been verified by this technique. Published online: 15 May 2001     

布尔函数的复杂系数及其应用

本文利用线性复杂度相关理论,给出了布尔函数复杂系数的定义：得出任何布尔函数的线性复杂度均等于这个函数的复杂系数;给出了一种快速求解布尔函数多项式表示的算法;研究了Bent函数的线性复杂度特点,利用布尔函数的复杂系数,得出布尔函数为Bent函数的一个必要条件。     

Evaluating spectral norms for constant depth circuits with symmetric gates

The Fourier spectrum and its norms are given as explicit arithmetic expressions and evaluated, for Boolean functions computed by classes of constant depth, read-once circuits consisting of an arbitrary set of symmetric gates. Previous results of this nature estimate the spectralL ₁ norm of functions computed by certain types of decision trees [20], [7], and in some cases, give randomizedprocedures that evaluate the spectrum by clever rounding [20]. One corollary of our results provides a large class ofAC ⁰ functions whose spectralL ₁ norm is exponential, thus generalizing the single example of such a function given in [9]. This shows that almost every read-onceAC ⁰ function does not belong in the classPL ₁ of functions with polynomially bounded spectral norms.Implications of our results and technique are discussed, for estimating the spectral norms ofany function in a constant depth circuit class, using the coding theoretic concept of weight distributions. Evaluating the spectral norms for any such function reduces to estimating certain non-trivial weight distributions of simple, linear codes.     

The Monotone Circuit Complexity of Quadratic Boolean Functions

Several results on the monotone circuit complexity and the conjunctive complexity, i.e., the minimal number of AND gates in monotone circuits, of quadratic Boolean functions are proved. We focus on the comparison between single level circuits, which have only one level of AND gates, and arbitrary monotone circuits, and show that there is an exponential gap between the conjunctive complexity of single level circuits and that of general monotone circuits for some explicit quadratic function. Nearly tight upper bounds on the largest gap between the single level conjunctive complexity and the general conjunctive complexity over all quadratic functions are also proved. Moreover, we describe the way of lower bounding the single level circuit complexity and give a set of quadratic functions whose monotone complexity is strictly smaller than its single level complexity.     

On the minimization of complexity and automation of efficient representation of boolean functions in classes of formulas and circuits

A method for synthesizing Boolean formulas intended for the efficient construction of circuit composed on functional elements, which is also suitable for minimal complexity circuits, is developed. Upper bounds on the implementation complexity of arbitrary Boolean functions in terms of the Zhegalkin basis are determined. A computational method for improving these bounds is proposed. A method for deriving certain countable classes of Boolean functions of minimal complexity is also recommended.     

On P versus NP $ \cap $ co-NP for decision trees and read-once branching programs

It is known that if a Boolean function f in n variables has a DNF and a CNF of size then f also has a (deterministic) decision tree of size exp(O(log n log² N)). We show that this simulation cannot be made polynomial: we exhibit explicit Boolean functions f that require deterministic trees of size exp where N is the total number of monomials in minimal DNFs for f and ?f. Moreover, we exhibit new examples of explicit Boolean functions that require deterministic read-once branching programs of exponential size whereas both the functions and their negations have small nondeterministic read-once branching programs. One example results from the Bruen—Blokhuis bound on the size of nontrivial blocking sets in projective planes: it is remarkably simple and combinatorially clear. Other examples have the additional property that f is in AC⁰. Received: June 5 1997.     

扩展Toffoli门及其在多输出电路设计中的应用

用量子计算电路实现布尔逻辑运算是发展量子计算的一个重要目标。提出了量子扩展Toffoli门,及其在实现多输出逻辑电路中的转换算法。该算法将传统PLA文件的SOP积项转换到实现等价逻辑功能的量子Toffoli积项,能够用量子扩展Toffoli门实现。通过MCNC基准电路的测试结果表明,与经典PLA描述相比,用扩展Toffoli门能够更有效地描述多输出逻辑函数。     

A lower bound method for quantum circuits

Quantum circuits, which are shallow, limited in the number of gates and additional workspace qubits, are popular for quantum computation because they form the simplest possible model similar to the classical model of a network of Boolean gates and capable of performing non-trivial computation. We give a new lower bound technique for such circuits and use it to give another proof that deterministic computation of the parity function cannot be performed by such circuits.     

The size and depth of layered Boolean circuits

We consider the relationship between size and depth for layered Boolean circuits and synchronous circuits. We show that every layered Boolean circuit of size s can be simulated by a layered Boolean circuit of depth . For synchronous circuits of size s, we obtain simulations of depth . The best known result so far was by Paterson and Valiant (1976) [17], and Dymond and Tompa (1985) [6], which holds for general Boolean circuits and states that , where C(f) and D(f) are the minimum size and depth, respectively, of Boolean circuits computing f. The proof of our main result uses an adaptive strategy based on the two-person pebble game introduced by Dymond and Tompa (1985) [6]. Improving any of our results by polylog factors would immediately improve the bounds for general circuits.     

Learning a circuit by injecting values

We propose a new model for exact learning of acyclic circuits using experiments in which chosen values may be assigned to an arbitrary subset of wires internal to the circuit, but only the value of the circuit's single output wire may be observed. We give polynomial time algorithms to learn (1) arbitrary circuits with logarithmic depth and constant fan-in and (2) Boolean circuits of constant depth and unbounded fan-in over AND, OR, and NOT gates. Thus, both AC0 and NC1 circuits are learnable in polynomial time in this model. Negative results show that some restrictions on depth, fan-in and gate types are necessary: exponentially many experiments are required to learn AND/OR circuits of unbounded depth and fan-in; it is NP-hard to learn AND/OR circuits of unbounded depth and fan-in 2; and it is NP-hard to learn circuits of constant depth and unbounded fan-in over AND, OR, and threshold gates, even when the target circuit is known to contain at most one threshold gate and that threshold gate has threshold 2. We also consider the effect of adding an oracle for behavioral equivalence. In this case there are polynomial-time algorithms to learn arbitrary circuits of constant fan-in and unbounded depth and to learn Boolean circuits with arbitrary fan-in and unbounded depth over AND, OR, and NOT gates. A corollary is that these two classes are PAC-learnable if experiments are available. Finally, we consider an extension of the model called the synchronous model. We show that an even more general class of circuits are learnable in this model. In particular, we are able to learn circuits with cycles.     

Verifying the determinant in parallel

In this paper, we investigate the complexity of verifying problems whose computation is equivalent to the determinant, both in the Boolean arithmetic circuit and in the Boolean circuit model. We observe that for a few problems, there exists an easy (NC ¹) verification algorithm. To characterize the harder ones, we define the class of problems that are reducible to the verification of the determinant, under two different reductions, and establish a list of complete problems in these classes. In particular, we prove that computing the rank is equivalent under AC ⁰ reductions to verifying the determinant. We show in the Boolean case that none of the complete problems can be recognized in NC ¹ unless L = NL. On the other hand, we show that for functions, there exists an NC ¹ checker even if they are hard to verify, and that they can be extended into functions whose verification is easy. received 24 August 1995     

Mathematical models for intellectualization of synthesis of discrete logical control units

A new method for studying mathematical models of discrete logical units based on functional equations is proposed. Representing Boolean functions in the class of formulas (circuits of functional elements with or without branching), we obtain the values of complexity indices in the number of characters, subformulas, and in the depth of a superposition formula (the number of functional elements and the circuit depth). The results are applied in the logical-computational approach to the intellectualization of synthesizing logical units on the basis of digital integrated circuits.     

Learning Read-Constant Polynomials of Constant Degree Modulo Composites

Boolean functions that have constant degree polynomial representation over a fixed finite ring form a natural and strict subclass of the complexity class ACC⁰. They are also precisely the functions computable efficiently by programs over fixed and finite nilpotent groups. This class is not known to be learnable in any reasonable learning model. In this paper, we provide a deterministic polynomial time algorithm for learning Boolean functions represented by polynomials of constant degree over arbitrary finite rings from membership queries, with the additional constraint that each variable in the target polynomial appears in a constant number of monomials. Our algorithm extends to superconstant but low degree polynomials and still runs in quasipolynomial time.     

Randomized vs. deterministic decision tree complexity for read-once Boolean functions

We consider the deterministic and the randomized decision tree complexities for Boolean functions, denotedDC(f) andRC(f), respectively. A major open problem is how smallRC(f) can be with respect toDC(f). It is well known thatRC(f)DC(f) ^0.5 for every Boolean functionf (called 0.5-exponent). On the other hand, some Boolean functionf is known to haveRC(f) = (DC(f))^0.753...) (or 0.753...-exponent). It is not known whether there is a Boolean function with exponent smaller than 0.753... Likewise, no lower bound for arbitrary Boolean functions with exponent greater than 0.5 is known.Our result is a 0.51 lower bound on the exponent for everyread-once function. Read-once means that each input variable appears exactly once in the Boolean formula representing the function. To obtain this result we generalize an existing lower bound technique and combine it with restriction arguments. This result provides a lower bound ofn ^0.51 on the number of positions that have to be evaluated by any randomized - pruning algorithm computing the value of any two-person zero-sum game tree withn final positions.     

Deeper Sparsely Nets can be Optimal

The starting points of this paper are two size-optimal solutions: (i) one for implementing arbitrary Boolean functions [1]; and (ii) another one for implementing certain sub-classes of Boolean functions [2]. Because VLSI implementations do not cope well with highly interconnected nets – the area of a chip grows with the cube of the fan-in [3] – this paper will analyse the influence of limited fan-in on the size optimality for the two solutions mentioned. First, we will extend a result from Horne & Hush [1] valid for fan-ins = 2 to arbitrary fan-in. Second, we will prove that size-optimal solutions are obtained for small constant fan-in for both constructions, while relative minimum size solutions can be obtained for fan-ins strictly lower than linear. These results are in agreement with similar ones proving that for small constant fan-ins ( = 6 ... 9), there exist VLSI-optimal (i.e., minimising AT2) solutions [4], while there are similar small constants relating to our capacity of processing information [5].     

Binary Decision Diagrams and neural networks

This paper describes a neural network approach that gives an estimation method for the space complexity of Binary Decision Diagrams (BDDs). A model has been developed to predict the complexity of digital circuits. The formal core of the developed neural network model (NNM) is a unique matrix for the complexity estimation over a set of BDDs derived from Boolean logic expressions with a given number of variables and Sum of Products (SOP) terms. Experimental results show good correlation between the theoretical results and those predicted by the NNM, which will give insights to the complexity of Very Large Scale Integration (VLSI)/Computer Aided Design (CAD) designs. The proposed model is capable of predicting the maximum BDD complexity (MaxBC) and the number of product terms (NPT) in the Boolean function that corresponds to the minimum BDD complexity (MinBC). This model provides an alternative way to predict the complexity of digital VLSI circuits.

Exponential lower bounds for depth three Boolean circuits

We consider the class of unbounded fan-in depth three Boolean circuits, for which the bottom fan-in is limited by k and the top gate is an OR. It is known that the smallest such circuit computing the parity function has gates (for k = O(n ^1/2)) for some , and this was the best lower bound known for explicit (P-time computable) functions. In this paper, for k = 2, we exhibit functions in uniform NC ¹ that require size depth 3 circuits. The main tool is a theorem that shows that any circuit on n variables that accepts a inputs and has size s must be constant on a projection (subset defined by equations of the form x _i = 0, x _i = 1, x _i = x _j or x _i = ) of dimension at least log(a/s)log n. Received: April 1, 1997.     

The Complexity of Deciding if a Boolean Function Can Be Computed by Circuits over a Restricted Basis

We study the complexity of the following algorithmic problem: Given a Boolean function f and a finite set of Boolean functions B, decide if there is a circuit with basis B that computes f. We show that if both f and all functions in B are given by their truth-table, the problem is in quasipolynomial-size AC⁰, and thus cannot be hard for AC⁰(2) or any superclass like NC¹, L, or NL. This answers an open question by Bergman and Slutzki (SIAM J. Comput., 2000). Furthermore we show that, if the input functions are not given by their truth-table but in a succinct way, i.e., by circuits (over any complete basis), the above problem becomes complete for the class coNP. Supported in part by DFG Grant Vo 630/5-2 and EPSRC Grant 531174.