Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR25-087 | 27th June 2025 11:36

Hardness Amplification for Real-Valued Functions

RSS-Feed




TR25-087
Authors: Yunqi Li, Prashant Nalini Vasudevan
Publication: 1st July 2025 01:32
Downloads: 42
Keywords: 


Abstract:

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 distribution $D^t$. We also show the same for the task of approximately computing real-valued functions $f: \{0,1\}^n \rightarrow [0,m)$. Our theorems immediately imply hardness self-amplification for several natural problems including Max-Clique and Max-SAT, Approximate $\#$SAT, Entropy Estimation, etc..



ISSN 1433-8092 | Imprint