Efficiently Testable Circuits
summary
Claims a compiler that maps any Boolean circuit C into Ĉ, T̂ compiler so the compiled circuit is functionally equivalent, increases size by only a constant factor (example: ~3× plus 3 control bits), and yields a testing set T̂ of size about 4·2^L that efficiently detects any wire tampering under the 1-conductive assumption. Construction uses control-bit XORs and layered multi-OR/multi-AND gadgets to turn every wire into one that is evaluated to both 0 and 1 across tests; depth grows modestly with L but the tester remains practical even for million-gate circuits.
AI-written summary · about
chapters (13)
- 0:00Intro
- 0:20Tampering the circuits
- 0:51Tampering model
- 3:37Previous works - heuristic testing
- 5:03Our approach
- 6:35Construction example
- 7:02Construction covering sets
- 9:32Construction - trivial solution for preprocessed circuits
- 11:34Construction - partial solution
- 14:54Construction - large depth solution
- 16:37Construction - efficient solution
- 18:26Compiler-parameters discussion
- 19:38Testing circuits - open problems
related talks
32mOptimal Quantum Programs
30mSymbolic Execution of Hadamard-Toffoli Quantum Circuits
37mJourney with Eric Allender: From Turing Machines to Circuits, and Back
51mOn constant T-depth circuits
19mAlgorithms and Lower Bounds for Comparator Circuits from Shrinkage
39mBuilding a Compiler for Quantum Computers
21mCut Tracing with E-Graphs for Boolean FHE Circuit Synthesis
20mCompilation of Qubit Circuits to Optimized Qutrit Circuits