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.     

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.     

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.     

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.     

An approximation method for high-order fractional derivatives of algebraically singular functions

The fractional derivative D^qf(s) (0≤s≤1) of a given function f(s) with a positive non-integer q is defined in terms of an indefinite integral. We propose a uniform approximation scheme to D^qf(s) for algebraically singular functions f(s)=s^αg(s) (α>−1) with smooth functions g(s). The present method consists of interpolating g(s) at sample points t_j in [0,1] by a finite sum of the Chebyshev polynomials. We demonstrate that for the non-negative integer m such that m<q<m+1, the use of high-order derivatives g⁽ⁱ⁾(0) and g⁽ⁱ⁾(1) (0≤i≤m) at both ends of [0,1] as well as g(t_j), t_j∈[0,1] in interpolating g(s), is essential to uniformly approximate D^q{s^αg(s)} for 0≤s≤1 when α≥q−m−1. Some numerical examples in the simplest case 1<q<2 are included.     

Binding number and Hamiltonian (g,f)-factors in graphs II

A (g, f)-factor F of a graph G is called a Hamiltonian (g, f)-factor if F contains a Hamiltonian cycle. For a subset X of V(G), let N _G (X)= gcup _x∈X N _G (x). The binding number of G is defined by bind(G)=min{| N _G (X) |/| X|| ?≠X?V(G), N _G (X)≠V(G)}. Let G be a connected graph of order n, 3≤a≤b be integers, and b≥4. Let g, f be positive integer-valued functions defined on V(G), such that a≤g(x)≤f(x)≤b for every x∈V(G). Suppose n≥(a+b?4)²/(a?2) and f(V(G)) is even, we shall prove that if bind(G)>((a+b?4)(n?1))/((a?2)n?(5/2)(a+b?4)) and for any independent set X?V(G), N _G (X)≥((b?3)n+(2a+2b?9)| X|)/(a+b?5), then G has a Hamiltonian (g, f)-factor.     

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.     

Diagonal polynomials and diagonal orders on multidimensional lattices

HereR andN denote the real numbers and the nonnegative integers, respectively. Alsos(x)=x ₁+···+x _n whenx=(x ₁, …,x _n) inR ⁿ. A mapf:R ⁿ →R is call adiagonal function of dimensionn iff|N ⁿ is a bijection ontoN and, for allx, y inN ⁿ, f(x)<f(y) whens(x)<s(y). Morales and Lew [6] constructed 2 ⁿ⁻² inequivalent diagonal polynomial functions of dimensionn for eachn>1. Here we use new combinatorial ideas to show that numberd _n of such functions is much greater than 2 ⁿ⁻² forn>3. These combinatorial ideas also give an inductive procedure to constructd _n+1 diagonal orderings of {1, …,n}.     

Some remarks on Bianchi type-II, VIII, and IX models

Within the scope of anisotropic non-diagonal Bianchi type-II, VIII, and IX spacetimes it is shown that the off-diagonal components of the Einstein equations impose severe restrictions on the components of the energy-momentum tensor (EMT) in general. We begin with a metric with three functions of time, a(t), b(t), and c(t), and two spatial ones, f(z) and h(z). It is shown that if the EMT is assumed to be diagonal, and f = f(z), in all cosmological models in question b ∝ c, and the matter distribution is isotropic, i.e., T ₁ ¹ = T ₂ ² = T ₃ ³ . If f = const, which is a special case of BII models, the matter distribution may be anisotropic, but only the z axis is distinguished, and in this case b(t) is not necessarily proportional to c(t).     

New explicit filters and smoothers for diffusions with nonlinear drift and measurements

The optimal least-squares filtering of a diffusion x(t) from its noisy measurements {y(τ); 0 τ t} is given by the conditional mean E[x(t)|y(τ); 0 τ t]. When x(t) satisfies the stochastic diffusion equation dx(t) = f(x(t)) dt + dw(t) and y(t) = ∫₀^tx(s) ds + b(t), where f(·) is a global solution of the Riccati equation /xf(x) + f(x)² = f(x)² = αx² + βx + γ, for some , and w(·), b(·) are independent Brownian motions, Benes gave an explicit formula for computing the conditional mean. This paper extends Benes results to measurements y(t) = ∫₀^tx(s) ds + ∫₀^t dx(s) + b(t) (and its multidimensional version) without imposing additional conditions on f(·). Analogous results are also derived for the optimal least-squares smoothed estimate E[x(s)|y(τ); 0 τ t], s < t. The methodology relies on Girsanov's measure transformations, gauge transformations, function space integrations, Lie algebras, and the Duncan-Mortensen-Zakai equation.     

Lower Bounds on Performance of Metric Tree Indexing Schemes for Exact Similarity Search in High Dimensions

Within a mathematically rigorous model, we analyse the curse of dimensionality for deterministic exact similarity search in the context of popular indexing schemes: metric trees. The datasets X are sampled randomly from a domain Ω, equipped with a distance, ρ, and an underlying probability distribution, μ. While performing an asymptotic analysis, we send the intrinsic dimension d of Ω to infinity, and assume that the size of a dataset, n, grows superpolynomially yet subexponentially in d. Exact similarity search refers to finding the nearest neighbour in the dataset X to a query point ω∈Ω, where the query points are subject to the same probability distribution μ as datapoints. Let denote a class of all 1-Lipschitz functions on Ω that can be used as decision functions in constructing a hierarchical metric tree indexing scheme. Suppose the VC dimension of the class of all sets {ω:f(ω)≥a}, a∈? is o(n ^1/4/log² n). (In view of a 1995 result of Goldberg and Jerrum, even a stronger complexity assumption d ^O(1) is reasonable.) We deduce the Ω(n ^1/4) lower bound on the expected average case performance of hierarchical metric-tree based indexing schemes for exact similarity search in (Ω,X). In paricular, this bound is superpolynomial in d.     

Minimal on-line labelling

The problem of on-line labelling is one of assigning integer labels in the range 1 to N to an input stream of at most N distinct items, drawn from a linearly ordered set, so that at each step the labels respect the ordering on the items. To maintain this constraint, items may have to be relabelled to accommodate new ones. With T(M,N) denoting the total number of relabellings that have to be performed for the first M inputs, it is known that for any given constant c in the range 0<c<1 there are exact bounds T(Nc,N)=Θ(NlogN) and T(cN,N)=Θ(Nlog²N). However, in the case c=1, when the labelling is called minimal, is known only that T(N,N)=O(Nlog³N). Existing algorithms for minimal on-line labelling are complicated, and our aim in this paper is to give a simplified and self-contained account of the problem.     

The privacy of dense symmetric functions

Ann argument function,f, is calledt-private if there exists a distributed protocol for computingf so that no coalition of at mostt processors can infer any additional information from the execution of the protocol. It is known that every function defined over a finite domain is [(n–1)/2]-private. The general question oft-privacy (fort[n/2]) is still unresolved.In this work, we relate the question of [n/2]-privacy for the class of symmetric functions of Boolean argumentsf: {0, 1} ⁿ {0, 1,...,n} to the structure of Hamming weights inf ^–1(b) (b{0, 1, ...,n}). We show that iff is [n/2]-private, then every set of Hamming weightsf ^–1(b) must be an arithmetic progression. For the class ofdense symmetric functions (defined in the sequel), we refine this to the following necessary and sufficient condition for [n/2]-privacy off: Every collection of such arithmetic progressions must yield non-identical remainders, when computed modulo the greatest common divisor of their differences. This condition is used to show that for dense symmetric functions, [n/2]-privacy impliesn-privacy.     

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.     

On the asymptotic complexity of rectangular matrix multiplication

The number of essential multiplications required to multiply matrices of size N×N and N×N^x is studied as a function f(x). Bounds to f(x) sharper than trivial ones are presented and the asymptotic behaviour of f(x) is studied. An analogous investigation is performed for the problem of multiplying matrices of size N×N^x and N^x×N^y.     

Erzeugende Funktionen bei Spline-Interpolation mit äquidistanten Knoten

Using generating functions we obtain in the case ofn+1 equidistant data points a method for the calculation of the interpolating spline functions(x) of degree 2k+1 with boundary conditionss ^(κ) (x₀)=y ₀ ^(κ) ,s ^(κ) (x _n )=y _n ^(κ) , κ=1(1)k, which only needs the inversion of a matrix of orderk. The applicability of our method in the case of general boundary conditions is also mentioned.     

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

An interpolation problem associated with H-optimal design in systems with distributed input lags

A variety of H^∞ optimal design problems reduce to interpolation of compressed multiplication operators, f(s) → π_k(w(s)f(s)), where w(s) is a given rational function and the subspace K is of the form K=H² φ(s)H². Here we consider φ(s) = (1-e^α-5)/(s - α), which stands for a distributed delay in a system's input. The interpolation scheme we develop, adapts to a broader class of distributed lags, namely, those determined by transfer functions of the form B(e^−s)/b(s), where B(z) and b(s) are polynomials and b(s) = 0 implies B(e^−s) = 0.     

Stable polyhedra in parameter space

A typical uncertainty structure of a characteristic polynomial is P(s)=A(s)Q(s)+B(s) with A(s) and B(s) fixed and Q(s) uncertain. In robust controller design Q(s) may be a controller numerator or denominator polynomial; an example is the PID controller with Q(s)=K_I+K_Ps+K_Ds². In robustness analysis Q(s) may describe a plant uncertainty. For fixed imaginary part of Q(jω), it is shown that Hurwitz stability boundaries in the parameter space of the even part of Q(jω) are hyperplanes and the stability regions are convex polyhedra. A dual result holds for fixed real part of Q(jω). Also σ-stability with the real parts of all roots of P(s) smaller than σ is treated.Under the above conditions, the roots of P(s) can cross the imaginary axis only at a finite number of discrete “singular” frequencies. Each singular frequency generates a hyperplane as stability boundary. An application is robust controller design by simultaneous stabilization of several representatives of A(s) and B(s) by a PID controller. Geometrically, the intersection of convex polygons must be calculated and represented tomographically for a grid on K_P.