Jeremiah Blocki

Amortized Relaxed Locally Decodable Codes

This work constructs the first aRLDC, an amortized relaxed locally decodable code (aRLDC), combining amortized decoding with the relaxed decoding paradigm, which is fully information-theoretic and makes no assumptions about shared randomness or computational limitations of the adversarial channel.