DNF are teachable in the average case

We study the average number of well-chosen labeled examples that are required for a helpful teacher to uniquely specify a target function within a concept class. This “average teaching dimension” has been studied in learning theory and combinatorics and is an attractive alternative to the “worst-case” teaching dimension of Goldman and Kearns which is exponential for many interesting concept classes. Recently Balbach showed that the classes of 1-decision lists and 2-term DNF each have linear average teaching dimension. As our main result, we extend Balbach’s teaching result for 2-term DNF by showing that for any 1≤s≤2 ^Θ(n), the well-studied concept classes of at-most-s-term DNF and at-most-s-term monotone DNF each have average teaching dimension O(ns). The proofs use detailed analyses of the combinatorial structure of “most” DNF formulas and monotone DNF formulas. We also establish asymptotic separations between the worst-case and average teaching dimension for various other interesting Boolean concept classes such as juntas and sparse GF ₂ polynomials.     

Error-Free and Best-Fit Extensions of Partially Defined Boolean Functions

In this paper, we address a fundamental problem related to the induction of Boolean logic: Given a set of data, represented as a set of binary “truen-vectors” (or “positive examples”) and a set of “falsen-vectors” (or “negative examples”), we establish a Boolean function (or an extension)f, so thatfis true (resp., false) in every given true (resp., false) vector. We shall further require that such an extension belongs to a certain specified class of functions, e.g., class of positive functions, class of Horn functions, and so on. The class of functions represents our a priori knowledge or hypothesis about the extensionf, which may be obtained from experience or from the analysis of mechanisms that may or may not cause the phenomena under consideration. The real-world data may contain errors, e.g., measurement and classification errors might come in when obtaining data, or there may be some other influential factors not represented as variables in the vectors. In such situations, we have to give up the goal of establishing an extension that is perfectly consistent with the given data, and we are satisfied with an extensionfhaving the minimum number of misclassifications. Both problems, i.e., the problem of finding an extension within a specified class of Boolean functions and the problem of finding a minimum error extension in that class, will be extensively studied in this paper. For certain classes we shall provide polynomial algorithms, and for other cases we prove their NP-hardness.     

The Complexity of the Descriptiveness of Boolean Circuits over Different Sets of Gates

Any Boolean function can be defined by a Boolean circuit, provided we may use sufficiently strong functions in its gates. On the other hand, what Boolean functions can be defined depends on these gate functions: Each set B of gate functions defines the class of Boolean functions that can be defined by circuits over B. Although these classes have been known since the 1920s, their computational complexity was never investigated.In this paper we will study how difficult it is to decide for a Boolean function f and a class B, whether f is in B.Moreover, we will provide such a decision algorithm with additional information: How difficult is it to decide whether or not f is in B, provided we already know a circuit for f, but with gates from another class A? Given such a circuit, we know that f is in A. Is the problem harder if we do not have a concrete representation for f, but still know that it is from A? For nearly all possible combinations, we show that this is not the case, and that the problem is either in P or coNP-complete.     

Boolean functions of an odd number of variables with maximum algebraic immunity

In this paper, we study Boolean functions of an odd number of variables with maximum algebraic immunity. We identify three classes of such functions, and give some necessary conditions of such functions, which help to examine whether a Boolean function of an odd number of variables has the maximum algebraic immunity. Further, some necessary conditions for such functions to have also higher nonlinearity are proposed, and a class of these functions are also obtained. Finally, we present a sufficient and necessary condition for Boolean functions of an odd number of variables to achieve maximum algebraic immunity and to be also 1-resilient.     

Boolean functions with long prime implicants

In this short note we introduce a hierarchy of classes of Boolean functions, where each class is defined by the minimum allowed length of prime implicants of the functions in the class. We show that for a given DNF and a given class in the hierarchy, it is possible to test in polynomial time whether the DNF represents a function from the given class. For the first class in the hierarchy we moreover present a polynomial time algorithm which for a given input DNF outputs a shortest logically equivalent DNF, i.e. a shortest DNF representation of the underlying function. This class is therefore a new member of a relatively small family of classes for which the Boolean minimization problem can be solved in polynomial time. For the second class and higher classes in the hierarchy we show that the Boolean minimization problem can be approximated within a constant factor.     

Lower Bounds on Learning Decision Lists and Trees

k-Decision lists and decision trees play important roles in learning theory as well as in practical learning systems.k-Decision lists generalize classes such as monomials,k-DNF, andk-CNF, and like these subclasses they are polynomially PAC-learnable [R. Rivest,Mach. Learning2(1987), 229–246]. This leaves open the question of whetherk-decision lists can be learned as efficiently ask-DNF. We answer this question negatively in a certain sense, thus disproving a claim in a popular textbook [M. Anthony and N. Biggs, “Computational Learning Theory,” Cambridge Univ. Press, Cambridge, UK, 1992]. Decision trees, on the other hand, are not even known to be polynomially PAC-learnable, despite their widespread practical application. We will show that decision trees are not likely to be efficiently PAC-learnable. We summarize our specific results. The following problems cannot be approximated in polynomial time within a factor of 2^{logδ n}for anyδ<1, unlessNP⊂DTIME[2^{polylog n}]: a generalized set cover,k-decision lists,k-decision lists by monotone decision lists, and decision trees. Decision lists cannot be approximated in polynomial time within a factor ofn^δ, for some constantδ>0, unlessNP=P. Also,k-decision lists withl0–1 alternations cannot be approximated within a factor log^l nunlessNP⊂DTIME[n^{O(log log n)}] (providing an interesting comparison to the upper bound obtained by A. Dhagat and L. Hellerstein [in“FOCS '94,” pp. 64–74]).     

Dualization, decision lists and identification of monotone discrete functions

Many data-analysis algorithms in machine learning, datamining and a variety of other disciplines essentially operate on discrete multi-attribute data sets. By means of discretisation or binarization also numerical data sets can be successfully analysed. Therefore, in this paper we view/introduce the theory of (partially defined) discrete functions as an important theoretical tool for the analysis of multi-attribute data sets. In particular we study monotone (partially defined) discrete functions. Compared with the theory of Boolean functions relatively little is known about (partially defined) monotone discrete functions. It appears that decision lists are useful for the representation of monotone discrete functions. Since dualization is an important tool in the theory of (monotone) Boolean functions, we study the interpretation and properties of the dual of a (monotone) binary or discrete function. We also introduce the dual of a pseudo-Boolean function. The results are used to investigate extensions of partially defined monotone discrete functions and the identification of monotone discrete functions. In particular, we present a polynomial time algorithm for the identification of so-called stable discrete functions. This revised version was published online in June 2006 with corrections to the Cover Date.     

Double Horn Functions

In this paper, we define double Horn functions, which are the Boolean functionsfsuch that bothfand its complement (i.e., negation)fare Horn, and investigate their semantical and computational properties. Double Horn functions embody a balanced treatment of positive and negative information in the course of the extension problem of partially defined Boolean functions (pdBfs), where a pdBf is a pair (T, F) of disjoint setsT, F⊆{0, 1}ⁿof true and false vectors, respectively, and an extension of (T, F) is a Boolean functionfthat is compatible withTandF. We derive syntactic and semantic characterizations of double Horn functions, and determine the number of such functions. The characterizations are then exploited to give polynomial time algorithms (i) that recognize double Horn functions from Horn DNFs (disjunctive normal forms), and (ii) that compute the prime DNF from an arbitrary formula, as well as its complement and its dual. Furthermore, we consider the problem of determining a double Horn extension of a given pdBf. We describe a polynomial time algorithm for this problem and moreover an algorithm that enumerates all double Horn extensions of a pdBf with polynomial delay. However, finding a shortest double Horn extension (in terms of the size of a formula?representing it) is shown to be intractable.     

Information loss in knowledge compilation: A comparison of Boolean envelopes

Since Selman and Kautz's seminal work on the use of Horn approximation to speed up the querying of knowledge bases, there has been great interest in Boolean approximation for AI applications. There are several Boolean classes with desirable computational properties similar to those of the Horn class. The class of affine Boolean functions, for example, has been proposed as an interesting alternative to Horn for knowledge compilation. To investigate the trade-offs between precision and efficiency in knowledge compilation, we compare, analytically and empirically, four well-known Boolean classes, and their combinations, for ability to preserve information. We note that traditional evaluation which explores unit-clause consequences of random hard 3-CNF formulas does not tell the full story, and we complement that evaluation with experiments based on a variety of assumptions about queries and the underlying knowledge base.     

Boolean Functions as Models for Quantified Boolean Formulas

In this paper, we introduce the notion of models for quantified Boolean formulas. For various classes of quantified Boolean formulas and various classes of Boolean functions, we investigate the problem of determining whether a model exists. Furthermore, we show for these classes the complexity of the model checking problem, which is to check whether a given set of Boolean functions is a model for a formula. For classes of Boolean functions, we establish some characterizations in terms of classes of quantified Boolean formulas that have such a model. This research has been supported in part by the Air Force Office of Scientific Research under grant FA9550-06-1-0050. This research has been supported in part by the NSFC under grants 60573011 and 10410638.     

Recognition of interval Boolean functions

Interval functions constitute a special class of Boolean functions for which it is very easy and fast to determine their functional value on a specified input vector. The value of an n-variable interval function specified by interval [a,b] (where a and b are n-bit binary numbers) is true if and only if the input vector viewed as an n-bit number belongs to the interval [a,b]. In this paper we study the problem of deciding whether a given disjunctive normal form represents an interval function and if so then we also want to output the corresponding interval. For general Boolean functions this problem is co-NP-hard. In our article we present a polynomial time algorithm which works for monotone functions. We shall also show that given a Boolean function f belonging to some class which is closed under partial assignment and for which we are able to solve the satisfiability problem in polynomial time, we can also decide whether f is an interval function in polynomial time. We show how to recognize a “renamable” variant of interval functions, i.e., their variable complementation closure. Another studied problem is the problem of finding an interval extension of partially defined Boolean functions. We also study some other properties of interval functions.      

On the Expressive Power of OKFDDs

Ordered Decision Diagrams (ODDs) as a means for the representation of Boolean functions are used in many applications in CAD. Depending on the decomposition type, various classes of ODDs have been defined, among them being the Ordered Binary Decision Diagrams (OBDDs), the Ordered Functional Decision Diagrams (OFDDs) and the Ordered Kronecker Functional Decision Diagrams (OKFDDs).Based on a formalization of the concept decomposition type we first investigate all possible decomposition types and prove that already OKFDDs, which result from the application of only three decomposition types, result in the most general class of ODDs. We then show from a (more) theoretical point of view that the generality of OKFDDs is really needed. We prove several exponential gaps between specific classes of ODDs, e.g. between OKFDDs on the one side and OBDDs, OFDDs on the other side. Combining these results it follows that a restriction of the OKFDD concept to subclasses, such as OBDDs and OFDDs as well, results in families of functions which lose their efficient representation.     

Learning Quickly When Irrelevant Attributes Abound: A New Linear-Threshold Algorithm

Valiant (1984) and others have studied the problem of learning various classes of Boolean functions from examples. Here we discuss incremental learning of these functions. We consider a setting in which the learner responds to each example according to a current hypothesis. Then the learner updates the hypothesis, if necessary, based on the correct classification of the example. One natural measure of the quality of learning in this setting is the number of mistakes the learner makes. For suitable classes of functions, learning algorithms are available that make a bounded number of mistakes, with the bound independent of the number of examples seen by the learner. We present one such algorithm that learns disjunctive Boolean functions, along with variants for learning other classes of Boolean functions. The basic method can be expressed as a linear-threshold algorithm. A primary advantage of this algorithm is that the number of mistakes grows only logarithmically with the number of irrelevant attributes in the examples. At the same time, the algorithm is computationally efficient in both time and space.     

布尔函数的统计独立性

定义在同一定义域上的两个布尔函数可能存在多种关系,本文研究它们之间的统计独立性,这种性质可以用于布尔置换的构造.本文给出了利用布尔函数的汉明距离判定两个布尔函数是否统计独立的充分必要条件,给出了寻找与某个已知布尔函数统计独立的布尔函数的算法,并分析了这种算法的有效性.     

Some lower bounds on the algebraic immunity of functions given by their trace forms

The algebraic immunity of a Boolean function is a parameter that characterizes the possibility to bound this function from above or below by a nonconstant Boolean function of a low algebraic degree. We obtain lower bounds on the algebraic immunity for a class of functions expressed through the inversion operation in the field GF(2 ⁿ ), as well as for larger classes of functions defined by their trace forms. In particular, for n ≥ 5, the algebraic immunity of the function Tr _n (x ^?1) has a lower bound ?2√n + 4? ? 4, which is close enough to the previously obtained upper bound ?√n? + ?n/?√n?? ? 2. We obtain a polynomial algorithm which, give a trace form of a Boolean function f, computes generating sets of functions of degree ≤ d for the following pair of spaces. Each function of the first (linear) space bounds f from below, and each function of the second (affine) space bounds f from above. Moreover, at the output of the algorithm, each function of a generating set is represented both as its trace form and as a polynomial of Boolean variables.     

Detection of global predicates: Techniques and their limitations

Summary. We show that the problem of predicate detection in distributed systems is NP-complete. In the past, efficient algorithms have been developed for special classes of predicates such as stable predicates, observer independent predicates, and conjunctive predicates. We introduce a class of predicates, semi-linear predicates, which properly contains all of the above classes. We first discuss stable, observer independent and semi-linear classes of predicates and their relationships with each other. We also study closure properties of these classes with respect to conjunction and disjunction. Finally, we discuss algorithms for detection of predicates in these classes. We provide a non-deterministic detection algorithm for each class of predicate. We show that each class can be equivalently characterized by the degree of non-determinism present in the algorithm. Stable predicates are defined as those that can be detected by an algorithm with the most non-determinism. All other classes can be derived by appropriately constraining the non-determinism in this algorithm.     

On the Nonlinearity and Correlation Immunity of Two Classes of Boolean Functions

Recently, Liu et al. have proved a class of 2k-variable Boolean functions to have optimal algebraic immunity and good immunity to fast algebraic attacks. In this paper, we proceed to study those functions in aspect of correlation immunity and nonlinearity and through restrictions to those functions we propose two sub-classes of 2k-variable Boolean functions with good cryptographic properties. To the best of our knowledge, this is the first time whole classes of Boolean functions with high nonlinearity, 1-correlation immunity and good immunity against FAA can be found.     

Limiting negations in bounded-depth circuits: An extension of Markov's theorem

A theorem of Markov shows the necessary and sufficient number of negations for computing an arbitrary collection of Boolean functions. In this paper, we consider a class of bounded-depth circuits, in which each gate computes an arbitrary monotone Boolean function or its negation. We show tight bounds on the number of negations for computing an arbitrary collection of Boolean functions when such a class of circuits is under consideration.