Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with direct product, testing, PCPs:
TR09-090 | 6th October 2009
Russell Impagliazzo, Valentine Kabanets, Avi Wigderson

New Direct-Product Testers and 2-Query PCPs

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 >>>

TR24-019 | 2nd February 2024
Yotam Dikstein, Irit Dinur, Alexander Lubotzky

Low Acceptance Agreement Tests via Bounded-Degree Symplectic HDXs

We solve the derandomized direct product testing question in the low acceptance regime, by constructing new high dimensional expanders that have no small connected covers. We show that our complexes have swap cocycle expansion, which allows us to deduce the agreement theorem by relying on previous work.

Derandomized direct product ... more >>>

ISSN 1433-8092 | Imprint