ISSN:
1573-7586
Keywords:
Boolean functions
;
independence
;
resilience
;
split orthogonal arrays
;
codes
;
bounds
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
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) = \frac{{2^{n - 2} }}{n}$$ , $$N(n,3,5) = \sqrt {\frac{{2^{n - 1} }}{n}}$$ , $$N(n,3,\frac{n}{2} - 1) = n$$ , $$N(n,\frac{n}{2} - 1,3) = n$$ , $$N(n,\frac{n}{2} - 1,5) = \sqrt {2n}$$ . We also find a connection of the problem considered with the construction of unequal-error-protection codes and superimposed codes for multiple access in the Hamming channel.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1023/A:1008207230165
Permalink
