This is a repost from the computer science stackexchange. The question has been offered a bounty, but received no answers. Therefore, I would like to ask this question here.
Orthogonal arrays often appear in probabilistic algorithms. They can be efficiently constructed from, e.g., BCH codes. But is there an efficient algorithm (better than brute force) that can verify if a binary array is orthogonal?
I don't see how there could be a deterministic algorithm to do this faster than brute force. Assume you have a $k\times N$ orthogonal array of strength $t.$ The statement of your question implies that no structural information other than the array itself is available.
This means any $t$ columns have all of the $2^{t}$ possible binary $t-$tuples occur the same number of times, say $\lambda,$ as one scans down the rows.
Now take a single entry of the array and switch it from $0$ to $1$ (complementing the OA gives another OA so this is fine). The problem will be that you cannot do a deterministic check without examining this entry.
If the strength $t$ is unknown, and you think an array is maybe not an OA, the most efficient method is checking that all columns are balanced. At worst, you might need to check $kN$ entries until finding the single entry that destroys the OA property. Then you'd start checking pairs of columns, etc.
If you know the strength is claimed to be $t$ and you want to check this you can have worst case complexity $\binom{k}{t}N$ until you examine all possible $t-$tuple balance conditions involving this entry.
As an aside, OAs are equivalent to what's called resilient functions in cryptography, see Stinson and Massey's paper "An infinite class of counterexamples to a conjecture concerning nonlinear resilient functions" in the Journal of Cryptology (vol. 8, pp. 167-172, 1995) [here].1 In some sense these are functions that leak minimal information if some of their inputs (meant to be secret) are revealed. They have shown that there are (a large set of) nonlinear OAs for this application where linear OAs with the same parameters do not exist.
*Edit: For linear OAs a faster test is possible as in Theorem 3.29 of Orthogonal Arrays: Theory and Applications by Hedayat et al.
