10 citations · 63 across the 24 of their papers we have counts for
Showing 2010 · cs.CCShow all
2 papers · 2 filters
cs.CC2010
Dense locally testable codes cannot have constant rate and distance
Irit Dinur, Tali Kaufman
A q-query locally testable code (LTC) is an error correcting code that can be tested by a randomized algorithm that reads at most q symbols from the given word. An important questi…
cs.CC2010
Derandomized Parallel Repetition via Structured PCPs
Irit Dinur, Or Meir
A PCP is a proof system for NP in which the proof can be checked by a probabilistic verifier. The verifier is only allowed to read a very small portion of the proof, and in return…