Revista Matemática Iberoamericana


Full-Text PDF (265 KB) | Metadata | Table of Contents | RMI summary
Volume 33, Issue 4, 2017, pp. 1351–1367
DOI: 10.4171/RMI/974

Published online: 2017-11-17

Various approaches for the study of the complexity of some families of pseudorandom subsets

Cécile Dartyge[1] and Domingo Gómez-Pérez[2]

(1) Université de Lorraine, Vandœuvre-lès-Nancy, France
(2) Universidad de Cantabria, Santandér, Spain

Studying randomness in different structures is important from the development of applications and theory. Dartyge, Mosaki and Sárközy (among others) have studied measures of randomness for families of subsets of integers. In this article, we improve results on the complexity of some families defined by polynomials, introducing new techniques from areas such as combinatorial geometry, geometry of numbers and additive combinatorics.

Keywords: Pseudorandomness, complexity

Dartyge Cécile, Gómez-Pérez Domingo: Various approaches for the study of the complexity of some families of pseudorandom subsets. Rev. Mat. Iberoamericana 33 (2017), 1351-1367. doi: 10.4171/RMI/974