Jul 2026
From Decision to Random Certificates: Exponential Separation for Edge Estimation with Independent Set Queries
A query model that preserves the structure of Independent Set queries, but augments their output with a random certificate is considered, which connects group testing, the decision-versus-counting dichotomy, graph property testing, and the power of a random certificate, and can be viewed as a structured form of conditi...
Debarshi Chanda, Buddha Dev Das, Arijit Ghosh et al.
· arXiv.org · 0 citations