Witness Sets

DOI10.1007/978-3-540-87448-5_5MaRDI QIDQ3540919zbMATH OpenOpenAlexFDO

Authors Gilles Zémor, Gérard Cohen, Hugues Randriam

Publication date 25 November 2008

Published in Coding Theory and Applications (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Linear codes (general theory) (94B05) Extremal set theory (05D05)

Abstract: Given a set C of binary n-tuples and c in C, how many bits of c suffice to distinguish it from the other elements in C? We shed new light on this old combinatorial problem and improve on previously known bounds.

Recommendations

• Witness sets for families of binary vectors
• Witnessing differences without redundancies
• Set membership with a few bit probes
• On the complexity of the identification problem in Hamming spaces
• Sets of binary sequences with small total Hamming distances

Cites work

• scientific article; zbMATH DE number 1324671 (Why is no real title available?)
• A Boolean measure of similarity
• Induced subsets
• Witness sets for families of binary vectors

Cited in

(5)

• Witness sets for families of binary vectors
• Separation and Witnesses
• Witness sets of projections
• Controlling witnesses
• Witnessing differences without redundancies

This page was built for publication: Witness Sets

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