🏅 Top traders

(testing nothing to see here)

Congrats @NateWatson! I will post my original solution in the side market https://manifold.markets/Incompleteusern/will-jats-claimed-solution-to-their.

@NateWatson good job on solving the problem!

Ok, here's a better writeup of @NateWatson's solution. If nobody has any complaints before I wake up tomorrow, I will resolve the market to YES.

https://latex.artofproblemsolving.com/miscpdf/lxfmitem.pdf?t=1769998851574

Screenshot

@jatloe is this similar to your original solution?

@jatloe Does this writeup justify the O(n^3) loops or do I have to reference Nate's solution for that?

@phenomist I think you can get it as follows:

Y has at most 2^n elements solely by the virtue of there being that many elements possible.

Each step multiplies the number of elements remaining from consideration by (1 - 1/100n^2).

For large n, we have that (1 - 1/100n^2)^(100n^2) is about 1/e, so after at most 200n^3 applications we've divided by e^(2n) > 2^n.

@NateWatson Ask me again when the market is resolved

@jatloe “T is in A…” it doesn’t follow the new set is smaller, just that it is in B minus X. The bound on the size of B is what provides the bound which is 100n loops.

@NateWatson Oh ok true.

I can fill in Proposition 1 if you really want (or someone can do it for me)

The algorithm only generates one query that tests 1/100n^2 of the possible Q. It can't cover all possible Q in a small number of queries.

1/100 n^ 2 of the remaining sets that need testing, not just of all possible. That's the Lovasz analysis referred to, if you have a greedy algorithm that knocks off a bounded fraction of the remainder each turn, you get a bound on the number of steps.

Can you (not an AI) describe how this "Lovasz analysis" works?

@DottedCalculator if you knock off a fixed proportion p each turn in a greedy algorithm, you get down to the point where there's only one left in log time for fixed p, then you can kill the last one in one more step

@NateWatson On page 3, you bounded N^(-1/(1+e/n)) below by N^-1. However, this means that on page 1, the actual bound you needed from proposition 1 was ln(u+alpha)/ln(u) < 1. Unrolling further, when you applied proposition 1, you used it to show (R^(1/S)+alpha)^S >= R^(1/(1+e alpha)). Since the bound you actually needed was just >= R, this implies alpha was useless, which of course makes no sense since the point is that A is being shrunk down faster than B is on the bottom of page 2. How are you using alpha nontrivially?

@jatloe alpha gets used twice in (2), your argument seems to be that one of these alphas is useless, but the other one could still be useful.

@harfe this seems to be the case. I will sanity check for a bit longer then provide a (much) better writeup of this solution and open it up to the NO holders to check

@harfe yeah I think the last step is really where the action is. It would be enough that I don’t decimate the to-miss set more than the to-hit set until the last step. Then we have to take a hit and chop it by a whole alpha to kill the last element.

@NateWatson Could you explain more how you select the next x in S to add to T? I am guessing you do not track $\mathcal C$ explicitly, as that would be exponential. But it somehow depends on $\mathcal C$ or previous Q's, otherwise you would just generate the same Q again and again.

I wanted to prove the sharpest version of theorem 1 which is kind of nice, independently of solving the problem. The generation of Q each turn uses the remainder (to miss) set which changes each time.

@NateWatson Yes, but HOW does it use the "to avoid" collection, without tracking the "to avoid" collection explicitly (which would be exponential)? (If the answer is simple enough, maybe you can provide pseudo code for that part).

@harfe you are allowed to track the "to avoid" collection explicitly since the problem only asks for subexponential queries, not subexponential time complexity.

@jatloe Thanks, that was what I missed! (I should have read the market description more carefully). Buying YES now.