6
This is impossible. No finite number of bits of $f(a_0,\dots,a_n)$ suffices to determine any of $a_0,\dots,a_n$; in fact, any nondegenerate real interval contains the values $f(a_0,\dots,a_n)$ for infinitely many vectors $(a_0,\dots,a_n)\in\mathbb Z^{n+1}$, and this holds even you fix all but two of the $a_0,\dots,a_n$ in advance.
3
If you know that the $a_i$'s are all not too large, and you have a good approximation to $f(a_0,\dots,a_n)$, I think LLL lattice basis reduction could be applicable (I haven't tried to verify the details).
Algorithms for finding integer relations look very closely related, and might possibly be directly applicable.
Only top voted, non community-wiki answers of a minimum length are eligible
Related Tags
cc.complexity-theory × 2745complexity-classes × 437
reference-request × 329
np-hardness × 316
ds.algorithms × 230
graph-theory × 226
circuit-complexity × 220
sat × 134
counting-complexity × 128
graph-algorithms × 126
time-complexity × 125
quantum-computing × 110
lower-bounds × 107
reductions × 80
approximation-algorithms × 75
approximation-hardness × 74
big-picture × 71
co.combinatorics × 70
lo.logic × 70
np × 68
boolean-functions × 67
computability × 58
cr.crypto-security × 57
optimization × 55
space-bounded × 54