The “direct product code” of a function f gives its values on all k-tuples (f(x1), . . . , f(xk)).
This basic construct underlies “hardness amplification” in cryptography, circuit complexity and
PCPs. Goldreich and Safra [GS00] pioneered its local testing and its PCP application. A recent
result by Dinur and ... more >>>