Case for unique solution sampler

[xuyoji]

I have a question on the case of unique solution.
If a sampler only outputs unique solutions(which means one valid solution can only appears once in the output), whether barbarik works correctly? In other words, whether the output data of barbarik is meaningful?
Thanks : )

[kuldeepmeel]

This is where the non-adversarial sampler assumption comes into the play. Ideally, barbarik should be able to catch a sampler that is not truly uniform sampler, since a truly uniform sampler would need to ensure that every solution occurs with equal probability and a deterministic sampler that simply enumerates solution may not necessarily do so.

Therefore, if barbarik is able to "catch", i.e., Reject the sampler, then one can use that output to debug the sampler but it is indeed possible that such an enumeration based algorithm may be able to fool barbarik. We would be very interested either way.

[msoos]

Let me chime in, being a bit pedantic perhaps :) You mentioned "a sampler only outputs unique solutions" -- please note that this is not correct uniform sampling in many cases. Let's say that there are 1k solutions, and you are asked to give 500 uniform samples at random. One is expected to find a number of repeated samples. A sampler that only outputs unique solutions will therefore not be a uniform sampler in this case. There are other "edge-cases", and particularly, heuristic "corners" that can make such a unique-solution-only solver non-viable and in fact highly dangerous, making the sampler seem uniform, when in fact it's not. Thankfully, Barbarik can often distinguish such samplers from truly uniform samplers :) I'm not sure I answered you question, but I wanted to highlight this perhaps easy-to-overlook aspect.