On the complexity of families of pseudo-random subsets (Q486751): Difference between revisions

From MaRDI portal
Importer (talk | contribs)
Created a new Item
 
Import241208061232 (talk | contribs)
Normalize DOI.
 
(7 intermediate revisions by 6 users not shown)
Property / DOI
 
Property / DOI: 10.5802/aif.2847 / rank
Normal rank
 
Property / author
 
Property / author: Sumit K. Garg / rank
 
Normal rank
Property / review text
 
Let \(p\) a prime, \(\mathbb{F}_{p}\) the finite field with \(p\) elements, \(S\subset \mathbb{F}_{p}\) and \(\mathcal{P}\subset\mathbb{F}_{p}[X]\) a set of polynomials of bounded degree \(\leq d\). The authors consider the problem to determine the integer \(k\) such that for all subsets \(\mathcal{A}, \mathcal{B}\subset\; \mathbb{F}_{p}\) satisfying \(\mathcal{A}\cap \mathcal{B}=\emptyset\) and \(|\mathcal{A}\cup \mathcal{B}| =k,\) there exists \(P\in \mathcal{P}\) such that \(P(x)\in S\) if \(x\in \mathcal{A}\) and \(P(x)\notin S\) if \(x\in \mathcal{B}\). This problem is related to the study of the complexity of certain pseudorandom subsets. The proofs are based on deep upper bounds for exponential sums and on character sums in finite fields. Furthermore, methods from additive number theory are used.
Property / review text: Let \(p\) a prime, \(\mathbb{F}_{p}\) the finite field with \(p\) elements, \(S\subset \mathbb{F}_{p}\) and \(\mathcal{P}\subset\mathbb{F}_{p}[X]\) a set of polynomials of bounded degree \(\leq d\). The authors consider the problem to determine the integer \(k\) such that for all subsets \(\mathcal{A}, \mathcal{B}\subset\; \mathbb{F}_{p}\) satisfying \(\mathcal{A}\cap \mathcal{B}=\emptyset\) and \(|\mathcal{A}\cup \mathcal{B}| =k,\) there exists \(P\in \mathcal{P}\) such that \(P(x)\in S\) if \(x\in \mathcal{A}\) and \(P(x)\notin S\) if \(x\in \mathcal{B}\). This problem is related to the study of the complexity of certain pseudorandom subsets. The proofs are based on deep upper bounds for exponential sums and on character sums in finite fields. Furthermore, methods from additive number theory are used. / rank
 
Normal rank
Property / reviewed by
 
Property / reviewed by: Robert F. Tichy / rank
 
Normal rank
Property / Mathematics Subject Classification ID
 
Property / Mathematics Subject Classification ID: 11K45 / rank
 
Normal rank
Property / Mathematics Subject Classification ID
 
Property / Mathematics Subject Classification ID: 11L07 / rank
 
Normal rank
Property / Mathematics Subject Classification ID
 
Property / Mathematics Subject Classification ID: 05B10 / rank
 
Normal rank
Property / zbMATH DE Number
 
Property / zbMATH DE Number: 6387274 / rank
 
Normal rank
Property / zbMATH Keywords
 
pseudo-random subsets
Property / zbMATH Keywords: pseudo-random subsets / rank
 
Normal rank
Property / zbMATH Keywords
 
complexity
Property / zbMATH Keywords: complexity / rank
 
Normal rank
Property / zbMATH Keywords
 
exponential sums
Property / zbMATH Keywords: exponential sums / rank
 
Normal rank
Property / zbMATH Keywords
 
character sums
Property / zbMATH Keywords: character sums / rank
 
Normal rank
Property / MaRDI profile type
 
Property / MaRDI profile type: MaRDI publication profile / rank
 
Normal rank
Property / OpenAlex ID
 
Property / OpenAlex ID: W2962769037 / rank
 
Normal rank
Property / arXiv ID
 
Property / arXiv ID: 1302.4622 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Exponential sums and Newton polyhedra: cohomology and estimates / rank
 
Normal rank
Property / cites work
 
Property / cites work: A complexity measure for families of binary sequences / rank
 
Normal rank
Property / cites work
 
Property / cites work: Incomplete Kloosterman sums and a divisor problem. Appendix: On some exponential sums by Bryan J. Birch and Enrico Bombieri / rank
 
Normal rank
Property / cites work
 
Property / cites work: On Exponential Sums in Finite Fields / rank
 
Normal rank
Property / cites work
 
Property / cites work: On large families of subsets of the set of the integers not exceeding \(N\) / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3505070 / rank
 
Normal rank
Property / cites work
 
Property / cites work: On pseudo-random subsets of the set of the integers not exceeding \(N\) / rank
 
Normal rank
Property / cites work
 
Property / cites work: On the pseudo-randomness of subsets related to primitive roots / rank
 
Normal rank
Property / cites work
 
Property / cites work: La conjecture de Weil. I / rank
 
Normal rank
Property / cites work
 
Property / cites work: On the Rationality of the Zeta Function of an Algebraic Variety / rank
 
Normal rank
Property / cites work
 
Property / cites work: Bounds for exponential sums and their applications to pseudorandom numbers / rank
 
Normal rank
Property / cites work
 
Property / cites work: Sum-free sets in abelian groups / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3949126 / rank
 
Normal rank
Property / cites work
 
Property / cites work: On \(p\)-pseudorandom binary sequences / rank
 
Normal rank
Property / cites work
 
Property / cites work: Number of Points of Varieties in Finite Fields / rank
 
Normal rank
Property / cites work
 
Property / cites work: Construction of pseudorandom binary sequences using additive characters / rank
 
Normal rank
Property / cites work
 
Property / cites work: On finite pseudorandom binary sequences I: Measure of pseudorandomness, the Legendre symbol / rank
 
Normal rank
Property / cites work
 
Property / cites work: Purity of exponential sums on 𝔸 n , II / rank
 
Normal rank
Property / cites work
 
Property / cites work: A finite pseudorandom binary sequence / rank
 
Normal rank
Property / cites work
 
Property / cites work: Equations over finite fields. An elementary approach / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4183410 / rank
 
Normal rank
Property / DOI
 
Property / DOI: 10.5802/AIF.2847 / rank
 
Normal rank
links / mardi / namelinks / mardi / name
 

Latest revision as of 18:56, 9 December 2024

scientific article
Language Label Description Also known as
English
On the complexity of families of pseudo-random subsets
scientific article

    Statements

    On the complexity of families of pseudo-random subsets (English)
    0 references
    0 references
    0 references
    16 January 2015
    0 references
    Let \(p\) a prime, \(\mathbb{F}_{p}\) the finite field with \(p\) elements, \(S\subset \mathbb{F}_{p}\) and \(\mathcal{P}\subset\mathbb{F}_{p}[X]\) a set of polynomials of bounded degree \(\leq d\). The authors consider the problem to determine the integer \(k\) such that for all subsets \(\mathcal{A}, \mathcal{B}\subset\; \mathbb{F}_{p}\) satisfying \(\mathcal{A}\cap \mathcal{B}=\emptyset\) and \(|\mathcal{A}\cup \mathcal{B}| =k,\) there exists \(P\in \mathcal{P}\) such that \(P(x)\in S\) if \(x\in \mathcal{A}\) and \(P(x)\notin S\) if \(x\in \mathcal{B}\). This problem is related to the study of the complexity of certain pseudorandom subsets. The proofs are based on deep upper bounds for exponential sums and on character sums in finite fields. Furthermore, methods from additive number theory are used.
    0 references
    pseudo-random subsets
    0 references
    complexity
    0 references
    exponential sums
    0 references
    character sums
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references