Classical Adversarial Fault-Tolerance and PCPs
2026-08-17 • Computational Complexity
Computational ComplexityInformation Theory
AI summaryⓘ
The authors explain a method to turn any regular computer circuit into one that still works well even if many bits are messed up on purpose at each step. They also show how to use a simpler version of this method, which only notices errors instead of fixing them, to build special proofs called probabilistically checkable proofs (PCPs) that need very few checks. This new way of making PCPs could help in developing similar proofs for quantum computers, based on earlier ideas by other researchers. Essentially, the work connects reliable computing with new types of proof systems.
fault-tolerant circuitsclassical circuitsbit corruptionprobabilistically checkable proofsPCPpolylogarithmic query complexityadversarial errorsquantum PCPcircuit compilationerror detection
Authors
Anurag Anshu, Nikolas P. Breuckmann, Louis Golowich, Quynh T. Nguyen, Umesh Vazirani
Abstract
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 provided a roadmap for constructing quantum PCPs via fault-tolerance.