Optimal randomised non-adaptive MIS reconstruction
Problem 5.2 (randomised non-adaptive optimality) · arXiv:2404.03472
Status open high confidence
Problem 5.2 asks whether the Ω(Δ²log(n/Δ)) lower bound for randomised non-adaptive MIS-query reconstruction algorithms is tight, i.e., whether an O(Δ²log(n/Δ)) algorithm exists. The current best upper bound remains O(Δ²log n) due to Konrad, O'Sullivan, and Traistaru (ITCS 2025), leaving a log Δ gap in the n-dependence. No follow-up paper closing this gap has been found as of May 2026.
Reviewer notes. The conjecture is posed against the backdrop of two contemporaneous papers: arXiv:2404.03472 (Michel–Scott, April 2024) proving the Ω(Δ²log(n/Δ)) lower bound, and arXiv:2401.05845 (Konrad–O'Sullivan–Traistaru, January 2024, published as ITCS 2025 LIPIcs proceedings) providing the O(Δ²log n) randomised non-adaptive upper bound. The ITCS 2025 proceedings version of arXiv:2401.05845 explicitly cites arXiv:2404.03472 (as reference [23]), confirming mutual awareness, but does not improve the upper bound. No subsequent paper achieving O(Δ²log(n/Δ)) was found across multiple searches covering 2024–2026.
Context
The paper proves an $\Omega(\Delta^{2}\log(n/\Delta))$ lower bound for randomised non-adaptive algorithms, while the existing upper bound of Konrad, O'Sullivan, and Traistaru is $\mathcal{O}(\Delta^{2}\log n)$. The question asks whether the new lower bound is tight, i.e., whether the $\log\Delta$ gap in the $n$-dependence can be closed.
Notes. Parser assigned the label 'Problem 5.0' to all three problems in Section 5; this is likely Problem 5.2 or the second of several unnumbered problems.
Source paper
Lower bounds for graph reconstruction with maximal independent set queries
Lukas Michel, Alex Scott · 2024-04-04
https://arxiv.org/abs/2404.03472