I think this works, but could be made a bit more clear/precise. We start with a list of all pairs (function, initial key). We begin by entering the key that would cause the first pair to open. If it does, done. If not, we know the state that the second pair on our list would be in. We enter the key that would cause it to open. If it does, done. If not, we know the state that the third pair would be in, etc. I guess this takes at most $m^n \cdot (m^n)^{m^n \cdot m^n}$ steps.

Agree with Jay's comment -- intuitively, the definition seems to need a modification. How about something like this? "$X \subset \mathbb{R}^2$ is $r$-convex if, for each $x \in X$, there exists a disk $D$ of radius $r$ such that $x \in D$ and $D \subseteq X$."

The abstract of Arora's original paper says "All our algorithms also work, with almost no modification, when distance is measured using any geometric norm (such as $\ell_p$ for $p \geq 1$ or other Minkowski norms)." graphics.stanford.edu/courses/cs468-06-winter/Papers/…

If sufficiently small perturbations of the edge weights do not harm a PTAS, the PTAS can't be tied to euclidicity of the instance -- I don't see why that follows....

Are you reading the question as "two points on the surface of the unit sphere", or ought this be overwhelmingly likely?

@sds, then maybe you can make some assumption about the distribution in terms of the subsets. Otherwise it may not be doable....

Is it important to the structure of the distribution that the observations are subsets? If we just think of the observations as integers between $1$ and $2^k$, then this sounds very hard: every distribution that is uniform on $\Omega(N^2)$ supports will look the same (no repeated samples), so distinguishing support size of $N^2$ from $2^k$ sounds impossible to me (but their entropies are very far apart).

It might help to note that, conditioned on the number of ones in $v$ (say there are $k$ of them), the $u_i$ are distributed i.i.d. $Bin(k,1/2)$.

Hmm, I think $C$ could be represented as a pair $(X',Y')$ with the same joint distribution as $(X,Y)$, with $h_1(A,X',Y') = X'$ and similarly for $h_2$.

You should try to make your model more formal and detailed. How many rounds are there? What does it mean to "communicate" between rounds? (Probably it doesn't matter for equilibrium analysis.) Do players keep the remainder that they choose not to bid?

@DouglasZare, by brute force I meant the ~$qp$ approach of finding one answer at a time.

Perhaps some ideas from coding or sphere-packing can help give a lower bound (I suspect you cannot do much better than brute-force search...). There is some target codeword in $\mathbb{Z}_q^p$ (the string of correct answers), your goal is to find a word within Hamming distance $0.1p$ of this target, and your only tool is to make Hamming-distance queries (how far is $x$ from the target?).

@FrançoisG.Dorais - you're right -- oops!! Thanks.

@FrançoisG.Dorais, to show hardness, I think we must reduce the other way: Given an arbitrary graph, show how to convert it to a bipartite graph whose domination number tells you the domination number of the original.

@Yemon,Paglia: agreed that it is not all that related, I just reacted without stopping to think about operator norms vs function norms and so on.

Maybe a good rewording/related question is "Holder's inequality for function composition", i.e. take Holder's inequality and replace $fg$ with $f \circ g$.

@MonroeEskew, the comments in Andres' link seem to conclude that the Baire Category Theorem can be cast as a diagonalization argument.