# 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 might want to look for strategies for solving Mastermind. – adrianN Oct 11 '17 at 15:12
• The usual rule is one question per post. – Yuval Filmus Oct 11 '17 at 20:11
• @YuvalFilmus I edited it to make it one question. – Josh Brown Kramer Oct 19 '17 at 17:23

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.
• This is very interesting. The introduction to the paper cited in the other post says "There are two cases of interest: (i) adaptive: the ith query is allowed to depend on all preceding queries and responses, and (ii) non-adaptive: the queries are formulated in advance. We only consider the non-adaptive case in this paper." I am interested in the adaptive case, which achieves much better results (more like $\log n$) when $|T|$ is much less than $|U|$. – Josh Brown Kramer Oct 19 '17 at 17:20