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.     

Improving bounds on link failure tolerance of the star graph

Determination of the minimum number of faulty links, f(n,k), that make every n-k-dimensional sub-star graph S_n-k faulty in an n-dimensional star network S_n, has been the subject of several studies. Bounds on f(n,k) have already been derived, and it is known that f(n,1)=n+2. Here, we improve the bounds on f(n,k). Specifically, it is shown that f(n,k)?(k+1)F(n,k), where F(n,k) is the minimum number of faulty nodes that make every S_n-k faulty in S_n. The complexity of f(n,k) is shown to be O(n²k) which is an improvement over the previously known upper bound of O(n³); this result in a special case leads to f(n,2)=O(n^↑2), settling a conjecture introduced in an earlier paper. A systematic method to derive the labels of the faulty links in case of f(n,1) is also introduced.     

Vasil’ev codes of length n = 2m and doubling of Steiner systems S(n, 4, 3) of a given rank

Extended binary perfect nonlinear Vasil’ev codes of length n = 2^m and Steiner systems S(n, 4, 3) of rank n-m over F ₂ are studied. The generalized concatenated construction of Vasil’ev codes induces a variant of the doubling construction for Steiner systems S(n, 4, 3) of an arbitrary rank r over F ₂. We prove that any Steiner system S(n = 2^m, 4, 3) of rank n-m can be obtained by this doubling construction and is formed by codewords of weight 4 of these Vasil’ev codes. The length 16 is studied in detail. Orders of the full automorphism groups of all 12 nonequivalent Vasil’ev codes of length 16 are found. There are exactly 15 nonisomorphic systems S(16, 4, 3) of rank 12 over F ₂, and they can be obtained from codewords of weight 4 of the extended Vasil’ev codes. Orders of the automorphism groups of all these Steiner systems are found.     

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.

     

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.     

Proper Learning Algorithm for Functions of k Terms under Smooth Distributions

In this paper, we introduce a probabilistic distribution, called a smooth distribution, which is a generalization of variants of the uniform distribution such as q-bounded distribution and product distribution. Then, we give an algorithm that, under the smooth distribution, properly learns the class of functions of k terms given as _k ^k_n={g(f₁(v), …, f_k(v)) | g _k, f₁, …, f_{k n}} in polynomial time for constant k, where _k is the class of all Boolean functions of k variables and _n is the class of terms over n variables. Although class _k ^k_n was shown by Blum and Singh to be learned using DNF as the hypothesis class, it has remained open whether it is properly learnable under a distribution-free setting.     

Robustness of star graph network under link failure

The star graph is an attractive underlying topology for distributed systems. Robustness of the star graph under link failure model is addressed. Specifically, the minimum number of faulty links, f(n, k), that make every (n − k)-dimensional substar S_n−k faulty in an n-dimensional star network S_n, is studied. It is shown that f(n,1)=n+2. Furthermore, an upper bound is given for f(n, 2) with complexity of O(n³) which is an improvement over the straightforward upper bound of O(n⁴) derived in this paper.     

On the lower bounds of the second order nonlinearities of some Boolean functions

The rth order nonlinearity of a Boolean function is an important cryptographic criterion in analyzing the security of stream as well as block ciphers. It is also important in coding theory as it is related to the covering radius of the Reed-Muller code R(r,n). In this paper we deduce the lower bounds of the second order nonlinearities of the following two types of Boolean functions:

1.

with d=2^2r+2^r+1 and , where n=6r.

2.

, where x,y∈F_2^t,n=2t,n?6 and i is an integer such that 1?i<t,gcd(2^t-1,2ⁱ+1)=1.

For some λ, the functions of the first type are bent functions, whereas Boolean functions of the second type are all bent functions, i.e., they possess the maximum first order nonlinearity. It is demonstrated that in some cases our bounds are better than the previously obtained bounds.     

On another Boolean matrix

In his paper “On a Boolean matrix”, Nechiporuk gave an explicit example of a set of n homogeneous monotone Boolean functions of the first degree in n variables that require Ω(n^3/2) two-input gates in any monotone Boolean network computing them. In this note we show how this can be extended to Ω(n^5/3) two-input gates.     

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).     

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.     

Cylindrical decomposition for systems transcendental in the first variable

We present a generalization of the Cylindrical Algebraic Decomposition (CAD) algorithm to systems of equations and inequalities in functions of the form p(x,f₁(x),…,f_m(x),y₁,…,y_n), where p∈Q[x,t₁,…,t_m,y₁,…,y_n] and f₁(x),…,f_m(x) are real univariate functions such that there exists a real root isolation algorithm for functions from the algebra Q[x,f₁(x),…,f_m(x)]. In particular, the algorithm applies when f₁(x),…,f_m(x) are real exp-log functions or tame elementary functions.     

The lower bounds on the second order nonlinearity of three classes of Boolean functions with high nonlinearity

The rth order nonlinearity of Boolean functions is an important cryptographic criterion associated with some attacks on stream and block ciphers. It is also very useful in coding theory, since it is related to the covering radii of Reed-Muller codes. This paper tightens the lower bounds of the second order nonlinearity of three classes of Boolean functions in the form f(x)=tr(x^d) in n variables, where (1) d=2^m+1+3 and n=2m, or (2) , n=2m and m is odd, or (3) d=2^2r+2^r+1+1 and n=4r.     

The Complexity of Boolean Functions in Different Characteristics

Every Boolean function on n variables can be expressed as a unique multivariate polynomial modulo p for every prime p. In this work, we study how the degree of a function in one characteristic affects its complexity in other characteristics. We establish the following general principle: functions with low degree modulo p must have high complexity in every other characteristic q. More precisely, we show the following results about Boolean functions f : {0, 1}ⁿ → {0, 1} which depend on all n variables, and distinct primes p, q:

Average-case analysis of the Modified Harmonic algorithm

In this paper we analyze the average-case performance of the Modified Harmonic algorithm for on-line bin packing. We first analyze the average-case performance for arbitrary distribution of item sizes over (0,1]. This analysis is based on the following result. Letf ₁ andf ₂ be two linear combinations of random variables {N _i } _i=1 ^k where theN _i 's have a joint multinomial distribution for eachn=σ _i=1 ^k ,N _i . LetE(f ₁) ≠ O andE(f ₂)≠ 0. Then lim_{n →}∞E(max(_{f 1},f ₂ ))/n = lim _n →∞ max(E(f ₁),E(f ₂))/n. We then consider the special case when the item sizes are uniformly distributed over (0,1]. For specific values of the parameters, the Modified Harmonic algorithm turns out to be better than the other two linear-time on-line algorithms—Next Fit and Harmonic—in both the worst case as well as the average case. We also obtain optimal values for the parameters of the algorithm from the average-case standpoint. For these values of the parameters, the average-case performance ratio is less than 1.19. This compares well with the performance ratios 1.333. and 1.2865. of the Next Fit algorithm and the Harmonic algorithm, respectively.     

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.     

On eliminating nondeterminism from turing machines which use less than logarithm worktape space

The graph accessibility problem restricted to graphs whose bandwidth is bounded by a function S(n), denoted by GAP(S(n)), is considered. An algorithm is presented to solve GAP(S(n)) deterministically in space log S(n)×logn,{GAP((S(n))^k)}_k?1 is a log space complete family of problems for NSPACE(logS(n)), for appropriately constructible S(n)∈O(n)?o(logn). Thus, for well-behaved S(n)∈O(logn)?O(loglogn), we obtain: NSPACE(S(n))?DSPACE(S(n)×logn).     

Results on rotation symmetric polynomials over GF(p)

In this paper, we generalize the recent counting results about rotation symmetric Boolean functions to the rotation symmetric polynomials over finite fields GF(p). By using Möbius function, we obtain some formulas for more general n, the number of variables. Some known formula in Boolean case are simplified.     

Komleva-type expansions and asymptotics for linear operators

In this paper, we prove asymptotic Komleva-type expansions valid for sequences of linear operators {T_n(·)} approximating the identity in supremum norm over the space of the continuous functions. In particular, under suitable mild conditions on the sequence {T_n(·)}, we obtain rational expansions for {T_n(f)} that are of special interest in a numerical analysis context. As special cases of these results, we find asymptotic expansions for exponential-type and De La Vallée Poussin polynomial operators. The case of the Cesaro sums is discussed in connection with the Komleva theory, but the main asymptotic results are proved by using other tools coming from a context of structured linear algebra. Some numerical applications of the theoretical part are then discussed.