MaxMinMax problem and sparse equations over finite fields

Asymptotical complexity of polynomial equation systems over finite field F-q is studied. Let X = {X-1, ... , X-m}, vertical bar boolean OR(m)(i=1) X-i vertical bar <= n be a fixed family of variable sets and the polynomials f(i) (X-i) are taken independently and uniformly at random from the set of all polynomials of degree <= q -1 in each of the variables in Xi. In particular, it is proved if vertical bar X-i vertical bar <= 3, m = n, then the average complexity of finding all solutions in F-q to f(i)(X-i) = 0 (1 <= i <= m) is at most (q)n/5.7883+ O(log n) for arbitrary X and q. The proof is based on a detailed analysis of MaxMinMax problem, a novel problem for hypergraphs.