Family complexity and VC-dimension

DOI10.1007/978-3-642-36899-8_15MaRDI QIDQ4915244zbMATH OpenOpenAlexFDO

Authors Christian Mauduit, András Sárközy

Publication date 9 April 2013

Published in Information Theory, Combinatorics, and Search Theory (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-36899-8_15

zbMATH Keywords

family complexitypseudorandomVC-dimension

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Research exposition (monographs, survey articles) pertaining to number theory (11-02) Pseudo-random numbers; Monte Carlo methods (11K45) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Recommendations

• On the complexity of a family related to the Legendre symbol
• A complexity measure for families of binary sequences
• Large Families of Pseudorandom Sequences of k Symbols and Their Complexity – Part II
• scientific article; zbMATH DE number 3890728
• Family complexity and cross-correlation measure for families of binary sequences

Cites work

• -nets and simplex range queries
• A complexity measure for families of binary sequences
• Construction of large families of pseudorandom binary sequences
• Construction of pseudorandom binary sequences using additive characters over \(GF(2^k)\)
• Construction of pseudorandom binary sequences using additive characters over GF(2ᵏ). II
• scientific article; zbMATH DE number 5619271 (Why is no real title available?)
• scientific article; zbMATH DE number 3908323 (Why is no real title available?)
• scientific article; zbMATH DE number 3630603 (Why is no real title available?)
• scientific article; zbMATH DE number 5247160 (Why is no real title available?)
• Large Families of Pseudorandom Sequences of k Symbols and Their Complexity – Part II
• Measures of pseudorandomness of families of binary lattices. I: Definitions, a construction using quadratic characters
• Measures of pseudorandomness of families of binary lattices. II: A further construction
• On a family of pseudorandom binary sequences
• On finite pseudorandom binary sequences I: Measure of pseudorandomness, the Legendre symbol
• On finite pseudorandom sequences of k symbols.
• On large families of subsets of the set of the integers not exceeding \(N\)
• On pseudo-random subsets of the set of the integers not exceeding \(N\)
• On pseudorandom binary lattices
• On the complexity of a family related to the Legendre symbol
• On the density of families of sets
• On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities

Cited in

(5)

• On the complexity of a family related to the Legendre symbol
• A complexity measure for families of binary sequences
• On the complexity of a family of Legendre sequences with irreducible polynomials
• A new lower bound on the family complexity of Legendre sequences
• On pseudorandomness of families of binary sequences

This page was built for publication: Family complexity and VC-dimension

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4915244)