Hardness Amplification beyond Boolean Functions

A central goal in average-case complexity is to understand how average-case hardness can be amplified to near-optimal hardness. Classical results such as Yao's XOR lemma establish this principle for Boolean functions, but these techniques typically apply only to artificially constructed functions, rather than to natural computational problems. In this work, we extend hardness amplification beyond the Boolean setting and extend the XOR Lemma to the sum of functions over the finite field F p , where p is a prime. Specifically, we show that if a function f : 0, 1 n → F p fails to be computed on at least a δ-fraction of inputs, then the k-wise sum

becomes almost optimally unpredictable: no efficient algorithm can compute it with success probability exceeding 1+ε p for suitable parameters k, δ, ε. Our proof is based on the pseudo-average-min entropy characterization of unpredictability due to Zheng (2014) and Vadhan and Zheng (2012), which we simplify and quantitatively refine to make the dependence of the circuit blow-up on all parameters fully explicit.

As an application, we obtain the first error-tolerant random self-reduction for a natural subgraph counting problem. Specifically, we show that any circuit that correctly counts triangles in an Erdős-Rényi random graph with noticeable probability can be transformed into a worstcase circuit with only a quasi-linear overhead.

We further extend the query lower bound framework of Shaltiel and Viola (2010) to the F p -valued setting, proving that any (possibly adaptive) black-box hardness amplification over F p must make at least Ω(p log(1/δ)/ε 2 ) oracle queries. Our proof substantially simplifies the core fixed-set lemma underlying previous analyses, offering a more modular and entropy-based argument.