Randomness turns out to be doing actual work: deterministic adaptive query answering dies after ~o(n) queries in the random-oracle model.

Black-box PIR with preprocessing gets lower bounds for free, sublinear online work still buys you linear-ish comms or server crypto.

Paper proving black-box PIR with preprocessing still hits lower bounds, so the free lunch is, naturally, imaginary.