MaxMinMax problem and sparse equations over finite fields (Q285259): Difference between revisions
From MaRDI portal
Latest revision as of 00:58, 12 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | MaxMinMax problem and sparse equations over finite fields |
scientific article |
Statements
MaxMinMax problem and sparse equations over finite fields (English)
0 references
19 May 2016
0 references
Let \(\mathbb F_q\) be the finite field with \(q\) elements and \(\mathcal X=\{ x_1, \ldots ,x_n\}\) be a set of variables. Consider a 3-sparse system of equations \[ f_1(X_1)=0, \ldots , f_m(X_m)=0, \] where each \(X_i\subset\mathcal X\), \(|X_i|\leq 3\) and the \(f_i\) are polynomials over \(\mathbb F_q\). The main result is that if \(m=n\) and the polynomials are taken independently and uniformly at random from the set of polynomials of degree \(\leq q-1\) in each variable then the average time complexity of finding all solutions in \(\mathbb F_q\) to the system has the upper bound \[ \frac{n}{q^{5.7883}}+\mathcal O(\log n). \] The underlying algorithm is the Gluing Algorithm introduced by the author in a previous paper [Des. Codes Cryptogr. 49, 47--60 (2008; Zbl 1196.11171); Math. Comput. Sci. 7, No. 3, 321--339 (2013; Zbl 1343.94080)]. This leads to needing an estimate on \[ \max_{\mathcal X}\min_{\pi}\max_{k} |\cup_{j=1}^k X_{\pi (j)}|-k, \] for permutations \(\pi\), an example of the \(\ell\)-MaxMinMax problem. The bulk of the paper consists of getting such an estimate.
0 references
finite fields
0 references
sparse equations
0 references
3-sets
0 references
maxminmax problem
0 references