Welcome to the resource topic for 2014/004
Title:
MaxMinMax problem and sparse equations over finite fields
Authors: Igor Semaev
Abstract:Asymptotical complexity of sparse equation systems over finite field F_q is studied. Let the variable sets belong to a fixed family \mathcal{X}=\{X_1,\ldots,X_m\} while the polynomials f_i(X_i) are taken independently and uniformly at random from the set of all polynomials of degree \leq q-1 in each of the variables in X_i. In particular, for |X_i|\le3, m=n, we prove the average complexity of finding all solutions to f_i(X_i)=0, i=1,\ldots,m by Gluing algorithm ( Semaev, Des. Codes Cryptogr., vol. 49 (2008), pp.47–60) is at most q^{\frac{n}{5.7883}+O(\log n)} for arbitrary \mathcal{X} and q. The proof results from a detailed analysis of 3-MaxMinMax problem, a novel problem for hyper-graphs.
ePrint: https://eprint.iacr.org/2014/004
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .