Original title: A Technique for Hardness Amplification Against $$\textsf{AC}^0$$
William M. Hoza · September 2026
Computer scientists often want to prove that simple computer circuits, called AC 0 circuits, cannot easily solve a specific math problem. A common method does this in three steps. First, it randomly fixes or simplifies the problem's inputs. Second, it shows that the circuit shrinks down into a basic step-by-step checklist, called a shallow decision tree. Third, it proves the simplified problem is still too tough for that checklist. In this paper, researchers found that any problem proven hard this way can be made much tougher. By combining several copies of the problem with an XOR operation—a rule comparing yes-or-no answers—the difficulty multiplies. They tested this on two famous hard problems and created a new decision tree tool.
Imagine you are packing a suitcase. Some items are bulky on their own, so one trick is to randomly remove clothes from each to make them easier to fit. But if you must pack all items together, the random removals interfere with each other, and the combined packing becomes much harder. In this paper, each bulky item is a function, the random removal is a restriction that simplifies the circuit, and XORing multiple copies is like packing everything together — it amplifies the overall difficulty.
Understanding what functions resist simple circuits helps us know limits of parallel computing. This work provides a general tool to amplify that resistance, turning a hard function into an even harder one. The technique applies to important known results, potentially strengthening lower bounds for tasks like learning and cryptography.
The technique only applies to hardness proofs that follow a specific structure: using random restrictions or projections to reduce circuits to shallow decision trees. It does not cover all possible proofs. The paper demonstrates the technique on two examples but does not establish full generality. The new XOR lemma for decision trees is proved, but its implications beyond this work are not explored.
Ask anything about this paper. Answers come from its abstract, and say so when the abstract doesn't cover your question.
A Technique for Hardness Amplification Against $$\textsf{AC}^0$$ — William M. Hoza — Computational Complexity — doi:10.1007/s00037-026-00296-9
Abstract licence: CC BY
Explanation generated by Synthesis from the abstract — it is not the original paper.