Algorithm to determine a set given the size of its intersection with sets you choose I am competing in a programming contest where the submission phase can be stated abstractly as follows : There is a known universe set, $U$, and a hidden target $T \subset U$.  I submit $S \subset U$, and for feedback I am given $|S \cap T|$.

What is a good/optimal strategy for finding $T$ in as few submissions as possible given no assumptions on the distribution of $T$?  What are the complexity bounds in terms of $|U|$ and $|T|$?  In my application, $|U|$ is in the tens of millions and $|T|$ has a known size of around 5000.
You are asking two questions. I will only answer the first, ignoring the fact that $|T|$ is much smaller than $|U|$. Your problem is very similar to the one tackled in this question. The same lower bound of $\Omega(n/\log n)$ holds here as well, where $n = |U|$. The same (apparently) matching upper bound also holds, since you can simulate a Hamming distance query using your kind of query.