{"id":"arxiv/2608.16860","url":"https://arxiv.org/abs/2608.16860","tags":["cs.CC","cs.IT","quant-ph"],"score":0,"title":"Classical Adversarial Fault-Tolerance and PCPs","domain":"cs.CC","source":"arxiv","authors":["Anurag Anshu","Nikolas P. Breuckmann","Louis Golowich","Quynh T. Nguyen","Umesh Vazirani"],"reviews":0,"subject":"cs.CC","summary":"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…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-08-17","reactions":{}}