On affine (non)equivalence of Boolean functions

In this paper we construct a multiset S(f) of a Boolean function f consisting of the weights of the second derivatives of the function f with respect to all distinct two-dimensional subspaces of the domain. We refer to S(f) as the second derivative spectrum of f. The frequency distribution of the weights of these second derivatives is referred to as the weight distribution of the second derivative spectrum. It is demonstrated in this paper that this weight distribution can be used to distinguish affine nonequivalent Boolean functions. Given a Boolean function f on n variables we present an efficient algorithm having O(n2²ⁿ ) time complexity to compute S(f). Using this weight distribution we show that all the 6-variable affine nonequivalent bents can be distinguished. We study the subclass of partial-spreads type bent functions known as PS _ap type bents. Six different weight distributions are obtained from the set of PS _ap bents on 8-variables. Using the second derivative spectrum we show that there exist 6 and 8 variable bent functions which are not affine equivalent to rotation symmetric bent functions. Lastly we prove that no non-quadratic Kasami bent function is affine equivalent to Maiorana–MacFarland type bent functions.     

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.     

Compact DSOP and Partial DSOP Forms

Given a Boolean function f on n variables, a Disjoint Sum-of-Products (DSOP) of f is a set of products (ANDs) of subsets of literals whose sum (OR) equals f, such that no two products cover the same minterm of f. DSOP forms are a special instance of partial DSOPs, i.e. the general case where a subset of minterms must be covered exactly once and the other minterms (typically corresponding to don’t care conditions of f) can be covered any number of times. We discuss finding DSOPs and partial DSOPs with a minimal number of products, a problem theoretically connected with various properties of Boolean functions and practically relevant in the synthesis of digital circuits. Finding an absolute minimum is hard, in fact we prove that the problem of absolute minimization of partial DSOPs is NP-hard. Therefore it is crucial to devise a polynomial time heuristic that compares favorably with the known minimization tools. To this end we develop a further piece of theory starting from the definition of the weight of a cube c as a functions of the number of fragments induced on other cubes by the selection of c, and show how cube weights can be exploited for building a class of minimization heuristics for DSOP and partial DSOP synthesis. A set of experiments conducted on major benchmark functions show that our method, with a family of variants, always generates better results than the ones of previous heuristics, including the method based on a BDD representation of f.     

On the degree of boolean functions as real polynomials

Every Boolean function may be represented as a real polynomial. In this paper, we characterize the degree of this polynomial in terms of certain combinatorial properties of the Boolean function. Our first result is a tight lower bound of Ω(logn) on the degree needed to represent any Boolean function that depends onn variables. Our second result states that for every Boolean functionf, the following measures are all polynomially related:

o The decision tree complexity off.

o The degree of the polynomial representingf.

o The smallest degree of a polynomialapproximating f in theL _max norm.

     

Block sensitivity of minterm-transitive functions

Boolean functions with a high degree of symmetry are interesting from a complexity theory perspective: extensive research has shown that these functions, if nonconstant, must have high complexity according to various measures.In a recent work of this type, Sun (2007) [9] gave lower bounds on the block sensitivity of nonconstant Boolean functions invariant under a transitive permutation group. Sun showed that all such functions satisfy bs(f)=Ω(N^1/3). He also showed that there exists such a function for which bs(f)=O(N^3/7lnN). His example belongs to a subclass of transitively invariant functions called “minterm-transitive” functions, defined by Chakraborty (2005) [3].We extend these results in two ways. First, we show that nonconstant minterm-transitive functions satisfy bs(f)=Ω(N^3/7). Thus, Sun’s example has nearly minimal block sensitivity for this subclass. Second, we improve Sun’s example: we exhibit a minterm-transitive function for which bs(f)=O(N^3/7ln^1/7N).     

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.     

Lower Bounds on the Query Complexity of Non-uniform and Adaptive Reductions Showing Hardness Amplification

Hardness amplification results show that for every Boolean function f, there exists a Boolean function Amp(f) such that if every size s circuit computes f correctly on at most a 1 ? δ fraction of inputs, then every size s′ circuit computes Amp(f) correctly on at most a ${1/2+\epsilon}$ fraction of inputs. All hardness amplification results in the literature suffer from “size loss” meaning that ${s' \leq \epsilon \cdot s}$ . We show that proofs using “non-uniform reductions” must suffer from such size loss. A reduction is an oracle circuit ${R^{(\cdot)}}$ which given oracle access to any function D that computes Amp(f) correctly on a ${1/2+\epsilon}$ fraction of inputs, computes f correctly on a 1 ? δ fraction of inputs. A non-uniform reduction is allowed to also receive a short advice string that may depend on both f and D. The well-known connection between hardness amplification and list-decodable error-correcting codes implies that reductions showing hardness amplification cannot be uniform for ${\epsilon < 1/4}$ . We show that every non-uniform reduction must make at least ${\Omega(1/\epsilon)}$ queries to its oracle, which implies size loss. Our result is the first lower bound that applies to non-uniform reductions that are adaptive, whereas previous bounds by Shaltiel & Viola (SICOMP 2010) applied only to non-adaptive reductions. We also prove similar bounds for a stronger notion of “function-specific” reductions in which the reduction is only required to work for a specific function f.     

Connections among nonlinearity,avalanche and correlation immunity

Nonlinear Boolean functions play an important role in the design of block ciphers, stream ciphers and one-way hash functions. Over the years researchers have identified a number of indicators that forecast nonlinear properties of these functions. Studying the relationships among these indicators has been an area that has received extensive research. The focus of this paper is on the interplay of three notable nonlinear indicators, namely nonlinearity, avalanche and correlation immunity. We establish, for the first time, an explicit and simple lower bound on the nonlinearity N_f of a Boolean function f of n variables satisfying the avalanche criterion of degree p, namely, N_f⩾2ⁿ⁻¹−2^{n−1−(1/2)p}. We also identify all the functions whose nonlinearity attains the lower bound. As a further contribution of this paper, we prove that except for very few cases, the sum of the degree of avalanche and the order of correlation immunity of a Boolean function of n variables is at most n−2. The new results obtained in this work further highlight the significance of the fact that while avalanche property is in harmony with nonlinearity, both go against correlation immunity.     

Recognition and dualization of disguised bidual Horn functions

We consider the problem of dualizing a Boolean function f given by CNF, i.e., computing a CNF for its dual f^d. While this problem is not solvable in quasi-polynomial total time in general (unless SAT is solvable in quasi-polynomial time), it is so in case the input belongs to special classes, e.g., the class of bidual Horn CNF ? [Discrete Appl. Math. 96-97 (1999) 55-88] (i.e., both ? and its dual ?^d represent Horn functions). In this paper, we show that a disguised bidual Horn CNF ? (i.e., ? becomes a bidual Horn CNF after renaming of variables) can be recognized in polynomial time, and its dualization can be done in quasi-polynomial total time. We also establish a similar result for dualization of prime CNFs.     

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.     

On lower bounds for read-k-times branching programs

A syntactic read-k-times branching program has the restriction that no variable occurs more thank times on any path (whether or not consistent) of the branching program. We first extend the result in [31], to show that the “n/2 clique only function”, which is easily seen to be computable by deterministic polynomial size read-twice programs, cannot be computed by nondeterministic polynomial size read-once programs, although its complement can be so computed. We then exhibit an explicit Boolean functionf such that every nondeterministic syntactic read-k-times branching program for computingf has size exp $$\left( {\Omega \left( {\frac{n}{{4^k k^3 }}} \right)} \right).$$      

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.     

Graph Complexity and Slice Functions

Abstract. A graph-theoretic approach to study the complexity of Boolean functions was initiated by Pudlák, Rödl, and Savický [PRS] by defining models of computation on graphs. These models generalize well-known models of Boolean complexity such as circuits, branching programs, and two-party communication complexity. A Boolean function f is called a 2-slice function if it evaluates to zero on inputs with less than two 1's and evaluates to one on inputs with more than two 1's. On inputs with exactly two 1's f may be nontrivially defined. There is a natural correspondence between 2-slice functions and graphs. Using the framework of graph complexity, we show that sufficiently strong superlinear monotone lower bounds for the very special class of {2-slice functions} would imply superpolynomial lower bounds over a complete basis for certain functions derived from them. We prove, for instance, that a lower bound of n ^1+Ω(1) on the (monotone) formula size of an explicit 2-slice function f on n variables would imply a 2 ^Ω(?) lower bound on the formula size over a complete basis of another explicit function g on l variables, where l=Θ( log n) . We also consider lower bound questions for depth-3 bipartite graph complexity. We prove a weak lower bound on this measure using algebraic methods. For instance, our result gives a lower bound of Ω(( log n) ³ / ( log log n) ⁵ ) for bipartite graphs arising from Hadamard matrices, such as the Paley-type bipartite graphs. Lower bounds for depth-3 bipartite graph complexity are motivated by two significant applications: (i) a lower bound of n ^Ω(1) on the depth-3 complexity of an explicit n -vertex bipartite graph would yield superlinear size lower bounds on log-depth Boolean circuits for an explicit function, and (ii) a lower bound of $\exp((\log \log n)^{\omega(1)})$ would give an explicit language outside the class Σ ₂ ^cc of the two-party communication complexity as defined by Babai, Frankl, and Simon [BFS]. Our lower bound proof is based on sign-representing polynomials for DNFs and lower bounds on ranks of ±1 matrices even after being subjected to sign-preserving changes to their entries. For the former, we use a result of Nisan and Szegedy [NS] and an idea from a recent result of Klivans and Servedio [KS]. For the latter, we use a recent remarkable lower bound due to Forster [F1].     

Circuit size is nonlinear in depth

Two fundamental complexity measures for a Boolean function f are its circuit depth d(f) and its circuit size c(f). It is shown that $\text{c?}\text{1}\text{4}\text{d·}\text{log}{}_2\text{d}$ for all f.     

A subclass of Horn CNFs optimally compressible in polynomial time

The problem of Horn Minimization (HM) can be stated as follows: given a Horn CNF representing a Boolean function f, find a shortest possible (optimally compressed) CNF representation of f, i.e., a CNF representation of f which consists of the minimum possible number of clauses. This problem is the formalization of the problem of knowledge compression for speeding up queries to propositional Horn expert systems, and it is known to be NP-hard. There are two subclasses of Horn functions for which HM is known to be solvable in polynomial time: acyclic and quasi-acyclic Horn functions. In this paper we define a new class of Horn functions properly containing both of the known classes and design a polynomial time HM algorithm for this new class.     

A very simple function that requires exponential size nondeterministic graph-driven read-once branching programs

Branching programs are a well-established computation model for Boolean functions, especially read-once branching programs (BP1s) have been studied intensively. A very simple function f in n² variables is exhibited such that both the function f and its negation ¬f can be computed by Σ³_p-circuits, the function f has nondeterministic BP1s (with one nondeterministic node) of linear size and ¬f has size O(n⁴) for oblivious nondeterministic BP1s but f requires nondeterministic graph-driven BP1s of size . This answers an open question stated by Jukna, Razborov, Savický, and Wegener [Comput. Complexity 8 (1999) 357-370].     

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.      

Linear complexity and autocorrelation values of a polyphase generalized cyclotomic sequence of length <Emphasis Type="Italic">pq</Emphasis>

A construction of a family of generalized polyphase cyclotomic sequences of length pq is presented in terms of the generalized cyclotomic classes modulo pq. Their linear complexity and corresponding minimal polynomials are deduced. Some upper bounds on periodic and aperiodic autocorrelation values of resulting sequences are also estimated by using certain exponential sums.     

Choosing,Agreeing, and Eliminating in Communication Complexity

We consider several questions inspired by the direct-sum problem in (two-party) communication complexity. In all questions, there are k fixed Boolean functions f ₁,…,f _k and each of Alice and Bob has k inputs, x ₁,…,x _k and y ₁,…,y _k , respectively. In the eliminate problem, Alice and Bob should output a vector σ₁,…,σ _k such that f _i (x _i , y _i ) ≠ σ _i for at least one i (i.e., their goal is to eliminate one of the 2 ^k output vectors); in the choose problem, Alice and Bob should return (i, f _i (x _i , y _i )), for some i (i.e., they choose one instance to solve), and in the agree problem they should return f _i (x _i , y _i ), for some i (i.e., if all the k Boolean values agree then this must be the output). The question, in each of the three cases, is whether one can do better than solving one (say, the first) instance. We study these three problems and prove various positive and negative results. In particular, we prove that the randomized communication complexity of eliminate, of k instances of the same function f, is characterized by the randomized communication complexity of solving one instance of f.