MaxMinMax problem and sparse equations over finite fields (Q285259): Difference between revisions
From MaRDI portal
Created a new Item |
Changed an Item |
||
Property / review text | |||
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. | |||
Property / review text: 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. / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 11T06 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 11Y16 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 68Q25 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 94A60 / rank | |||
Normal rank | |||
Property / zbMATH DE Number | |||
Property / zbMATH DE Number: 6582296 / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
finite fields | |||
Property / zbMATH Keywords: finite fields / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
sparse equations | |||
Property / zbMATH Keywords: sparse equations / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
3-sets | |||
Property / zbMATH Keywords: 3-sets / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
maxminmax problem | |||
Property / zbMATH Keywords: maxminmax problem / rank | |||
Normal rank |
Revision as of 19:29, 27 June 2023
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