Anzeige
Erschienen in:
2008 | OriginalPaper | Buchkapitel
Small Linear Dependencies for Binary Vectors of Low Weight
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
We show that every set of
$$ m \simeq cn \sqrt {n log log n} $$
vectors in {0, 1}
n
in which every vector has Hamming weight 3 contains a subset of {ti
O
(log
n
) vectors that form a linear dependency. Our proof is based on showing that in every graph of average degree at least
c
log log
n
, every legal edge coloring produces a cycle in which one of the colors appears either once or twice.} (In both results,
c
is some constant.) The results proved are used (in a companion work) in refutation algorithms for semirandom 3CNF formulas.