Sharp Threshold Rates for Random Codes
summary
Characterizes exact threshold rates for a wide class of monotone symmetric properties of completely random codes: R = 1 − max_tau H_q(tau)/b, shows these thresholds are sharp, and proves tightness of the union-bound lower bound by using the second moment method* for histogram types. Provides an algorithm to compute noisy list-recovery thresholds to any additive error, gives a closed-form threshold for binary p=3 list-decoding, and computes the threshold for perfect hashing; methods distinguish random from random-linear codes.
AI-written summary · about