On (2n/3-1)-resilient (n,2)-functions
share
A {00,01,10,11}-valued function on the vertices of the n-cube is called a t-resilient (n,2)-function if it has the same number of 00s, 01s, 10s and 11s among the vertices of every subcube of dimension t. The Friedman and Fon-Der-Flaass bounds on the correlation immunity order say that such a function must satisfy t< 2n/3-1; moreover, the (2n/3-1)-resilient (n,2)-functions correspond to the equitable partitions of the n-cube with the quotient matrix [[0,r,r,r],[r,0,r,r],[r,r,0,r],[r,r,r,0]], r=n/3. We suggest constructions of such functions and corresponding partitions, show connections with Latin hypercubes and binary 1-perfect codes, characterize the non-full-rank and the reducible functions from the considered class, and discuss the possibility to make a complete characterization of the class.
READ FULL TEXT