A trusted source of independent and uniform random bits is a basic resource in many computational tasks, such as cryptography, game theoretic protocols, algorithms and physical simulations. Implementing such a source presents an immediate challenge: how can one certify whether one has succeeded? i.e. suppose someone were to claim that a particular device outputs a uniformly random n-bit string; is there a feasible test to verify that claim?
Locally decodable codes (LDCs) are error-correcting codes that allow for highly-efficient recovery of "pieces" of information even after arbitrary corruption of a codeword. Locally testable codes (LTCs) are those that allow for highly-efficient testing to see if some given word is close to a codeword. Codes derived from evaluations of low-degree multivariate polynomials give the simplest