Split ortogonal arrays and maximum independent resilient systems of functions

Abstract:

A system of (Boolean) functions in n variables is called randomized if the functions preserve the property of their variables to be independent and uniformly distributed random variables. Such a system is referred to as t-resilient if for any substitution of constants for any i variables, where 0 ≤ i ≤ t, the derived system of functions in n-i variables will be also randomized. We investigate the problem of finding the maximum number N(n,t,T) of functions in n variables of which any T form a t-resilient system. This problem is reduced to the minimization of the size of certain combinatorial designs, which we call split orthogonal arrays. We extend some results of design and coding theory, in particular, a duality in bounding the optimal sizes of codes and designs, in order to obtain upper and lower bounds on N(n,t,T). In some cases, these bounds turn out to be very tight. In particular, for some infinite subsequences of integers n they allow us to prove that N(n,3,3)=2^{n-2}/n, N(n,3,5)=√(2^{n-1}/n), N(n,3,n/2-1)=n, N(n,n/2-1,3)=n, N(n,n/2-1,5)=√(2n).

Keywords:

code, design, Boolean functions, randomisation, resilience, upper and lower bounds.

Publication language:english, pages:29

Research direction:

Mathematical problems and theory of numerical methods