Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > YUNQI LI:
All reports by Author Yunqi Li:

TR25-087 | 27th June 2025
Yunqi Li, Prashant Nalini Vasudevan

Hardness Amplification for Real-Valued Functions

Given an integer-valued function $f:\{0,1\}^n\rightarrow \{0,1,\dots, m-1\}$ that is mildly hard to compute on instances drawn from some distribution $D$ over $\{0,1\}^n$, we show that the function $g(x_1, \dots, x_t) = f(x_1) + \dots + f(x_t)$ is strongly hard to compute on instances $(x_1, \dots, x_t)$ drawn from the product ... more >>>




ISSN 1433-8092 | Imprint