Hardness results for queries with preprocessing

Dear all,

I need some hardness results for some problems stated like follows:

Consider infinite sets A,B that contain (...) and function
f: AxB -> Bool
that computes (...).

The hardness result should say something like

There is no data structure for elements of A so that for any fixed a in A, given this data structure for a, the query
fa : B -> Bool, b |-> f(a,b)
can be answered faster than computing f directly with the usual presentation of elements of A.

Or if such data structures existed, then some widely accepted conjecture like Riemanns Hypothesis would be false.


Ideas, references?
Sasha.
.