Witness Sets

DOI10.1007/978-3-540-87448-5_5zbMATH Open1166.05311arXiv0902.0583OpenAlexW2913855297MaRDI QIDQ3540919FDOQ3540919

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)

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.

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

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

Mathematics Subject Classification ID

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

Cites Work

• Induced subsets
• Title not available (Why is that?)
• A Boolean measure of similarity
• Witness sets for families of binary vectors

Cited In (5)

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

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)