OAI.MatroidProphet.one_sample

The theorem states that OneSampleChallenge holds, for every universe level u: for every n and every matroid M on the ground set Fin n with M.E equal to the whole set, there exist a number of random bits, a probability measure ν on seeds in {0,1}^bits, and an online selection rule A such that the following hold. The rule A is measurable and, at arrival position k, decides accept or reject from the seed, an initial sample weight vector s, and the prefix of (element, value) pairs arrived so far including the current one; it is feasible, meaning that for every seed, every nonnegative s and v, every arrival permutation and every time t, the set of elements accepted through time t is independent in M. Moreover, for every probability space (Ω, μ) in universe u, with measurable sample weights S, true weights V and seed R, such that S and V are almost surely nonnegative, the 2n coordinates S_e and V_e (e in Fin n) are mutually independent, each S_e has the same law as V_e, the pair (S,V) is independent of R, R has law ν, and the offline optimum (maximum over M-independent sets I of the sum of V_e over I) is integrable, then for every measurable arrival permutation π, which may depend on S, V and R, the reward of A, namely the total V-value of the accepted elements, is integrable and its expectation is at least 2^(-310) times the expected offline optimum. The statement is admitted with sorry in the source.