Hash-cell occupancy amplification -- definitions

An amplified occupancy test draws an odd number of independent hash seeds and returns the strict majority of the corresponding nonempty-cell answers.

def Complexity.PairwiseIndependentHash.majoritySeedWidth (seedWidth errorBits : ℕ) : ℕ

Number of random bits used to amplify one seedWidth-bit occupancy test to error at most 2^-errorBits.

Equations

• Complexity.PairwiseIndependentHash.majoritySeedWidth seedWidth errorBits = (12 * errorBits + 1) * seedWidth

def Complexity.PairwiseIndependentHash.majorityNonempty {domainWidth rangeWidth seedWidth : ℕ} (hash : PairwiseIndependentHash domainWidth rangeWidth seedWidth) (set : Finset (BitString domainWidth)) (target : BitString rangeWidth) (errorBits : ℕ) (seed : BitString (majoritySeedWidth seedWidth errorBits)) : Bool

Strict majority of independent target-cell nonemptiness tests.

Equations

• hash.majorityNonempty set target errorBits seed = Complexity.blockMajority (hash.nonemptyCellEvent set target) seed

def Complexity.PairwiseIndependentHash.majorityNonemptyEvent {domainWidth rangeWidth seedWidth : ℕ} (hash : PairwiseIndependentHash domainWidth rangeWidth seedWidth) (set : Finset (BitString domainWidth)) (target : BitString rangeWidth) (errorBits : ℕ) : Finset (BitString (majoritySeedWidth seedWidth errorBits))

Seeds on which the amplified target-cell occupancy test returns true.

Equations

• One or more equations did not get rendered due to their size.

def Complexity.PairwiseIndependentHash.majorityEmptyEvent {domainWidth rangeWidth seedWidth : ℕ} (hash : PairwiseIndependentHash domainWidth rangeWidth seedWidth) (set : Finset (BitString domainWidth)) (target : BitString rangeWidth) (errorBits : ℕ) : Finset (BitString (majoritySeedWidth seedWidth errorBits))

Seeds on which the amplified target-cell occupancy test returns false.

Equations

• One or more equations did not get rendered due to their size.