(2,1)-separating systems beyond the probabilistic bound

DOI10.1007/S11856-012-0126-9zbMATH Open1381.94124arXiv1010.5764OpenAlexW2963795501MaRDI QIDQ375844FDOQ375844

Hugues Randriam

Publication date: 1 November 2013

Published in: Israel Journal of Mathematics (Search for Journal in Brave)

Abstract: Building on previous results of Xing, we give new lower bounds on the rate of intersecting codes over large alphabets. The proof is constructive, and uses algebraic geometry, although nothing beyond the basic theory of linear systems on curves. Then, using these new bounds within a concatenation argument, we construct binary (2,1)-separating systems of asymptotic rate exceeding the one given by the probabilistic method, which was the best lower bound available up to now. This answers (negatively) the question of whether this probabilistic bound was exact, which has remained open for more than 30 years. (By the way, we also give a formulation of the separation property in terms of metric convexity, which may be an inspirational source for new research problems.)

Full work available at URL: https://arxiv.org/abs/1010.5764

Recommendations

• Bounds on the rate of separating codes
• New upper bounds on cardinality of separating systems
• On pair-separating codes
• Dual fail-safe separating systems
• A note on \(\overline{2} \)-separable codes and \(B_2\) codes

Mathematics Subject Classification ID

Linear codes (general theory) (94B05) Bounds on codes (94B65) Geometric methods (including applications of algebraic geometry) applied to coding theory (94B27)

Cites Work

• Linear intersecting codes
• The probabilistic method. With an appendix on the life and work of Paul Erdős.
• Algebraic function fields and codes
• Frameproof Codes
• Collusion-secure fingerprinting for digital data
• Weierstrass Points and Curves Over Finite Fields
• Asymptotic bounds on frameproof codes
• Title not available (Why is that?)
• A tower of Artin-Schreier extensions of function fields attaining the Drinfeld-Vladut bound
• Modular curves, Shimura curves, and Goppa codes, better than Varshamov-Gilbert bound
• Title not available (Why is that?)
• Linear binary codes with intersection properties
• Number of points of an algebraic curve
• On the extremal combinatorics of the Hamming space
• Wronskians and Plücker formulas for linear systems on curves
• A new approach to error-correcting codes
• Combinatorial Properties and Constructions of Traceability Schemes and Frameproof Codes
• Weierstrass points in characteristic p

Cited In (13)

• Gaps between prime numbers and tensor rank of multiplication in finite fields
• Yet another variation on minimal linear codes
• Improved upper bounds for the rate of separating and completely separating codes
• Dual fail-safe separating systems
• Too Acute to Be True: The Story of Acute Sets
• General position sets in two families of Cartesian product graphs
• Bilinear complexity of algebras and the Chudnovsky-Chudnovsky interpolation method
• New upper bounds on cardinality of separating systems
• On general position sets in Cartesian products
• Separable collusion-secure multimedia codes
• Trisymmetric multiplication formulae in finite fields
• On the tensor rank of multiplication in finite extensions of finite fields and related issues in algebraic geometry
• On pair-separating codes

This page was built for publication: \((2,1)\)-separating systems beyond the probabilistic bound

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