Linear hashing by field multiplication and additive projection #
Multiply the source by a uniformly chosen field element, then apply an additive projection. Surjectivity of the projection gives the universal collision bound. In binary coefficient coordinates, projection onto an initial segment is the multiply-and-truncate construction used in Guruswami--Umans--Vadhan (2009), Lemma 5.1: https://people.seas.harvard.edu/~salil/research/PVcondenser-jacm.pdf. The seed ranges over the entire field, including zero.
def
Algebraic.Cutwidth.Extractor.fieldHash
{F : Type u_1}
{Ω : Type u_2}
[Field F]
[AddCommGroup Ω]
(projection : F →+ Ω)
(source seed : F)
:
Ω
Multiply by the field seed and apply an additive projection.
Equations
- Algebraic.Cutwidth.Extractor.fieldHash projection source seed = projection (seed * source)