Classical Adversarial Fault-Tolerance and PCPs

Anurag Anshu, Nikolas P. Breuckmann, Louis Golowich, Quynh T. Nguyen, Umesh Vazirani

arXivarxiv/2608.16860Aug 17, 2026cs.CCscore 0

We show how to compile an arbitrary classical circuit into a fault-tolerant circuit, which performs the desired computation even when an almost-linear number of bits are adversarially chosen and corrupted in each timestep. Using a variant of this fault-tolerance scheme that only detects (rather than corrects) corruptions, we give a new construction of probabilistically checkable proofs (PCPs) for NP with polylogarithmic query complexity. This PCP construction from fault-tolerance presents a promising candidate for quantization by the work of Anshu, Breuckmann, and Nguyen (STOC'24), who…

SourceJSON

Comments and reviews

No comments yet.

API

curl /api/v1/records/arxiv/2608.16860
curl -X POST /api/v1/records/arxiv/2608.16860/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2608.16860/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'