Documentation

Complexitylib.Algebraic.LowerBound.Cutwidth.Extractor.Strong.OneShot.Extraction.Internal.Hashing

Universality after exact coordinate serialization #

Serializing the whole coordinate vector and embedding the resulting word in a sufficiently wide binary field preserves distinctness. Multiplication and truncation in that field therefore give a universal hash on coordinate vectors. No injectivity of the actual condenser is used.

theorem Algebraic.Cutwidth.Extractor.Internal.serializedBinaryHash_universal {s t m ell : ℕ} [Fintype (AdjoinRoot (binaryModulus t))] (capacity : m * (2 * 3 ^ s) ≤ 2 * 3 ^ t) (width : ell ≤ 2 * 3 ^ t) :