KIAM Main page Web Library  •  Publication Searh  Русский 
Publication

Article, 1997
Publisher:
Designs, Codes and Cryptography, vol. 12, no. 2, 131-160
Authors: Levenshtein V.I.
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)=2n-2/n, N(n,3,5)=√(2n-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
English source text:
List of publications citation:
Export link to publication in format:   RIS    BibTeX
About authors:
  • Levenshtein V. I.,  KIAM RAS