Future-edge algorithm conjecture for balanced independent sets

Let GG be the graph in the paper's online model, let A(G)\mathcal{A}(G) be the set selected by an online algorithm A\mathcal{A}, and let EE be the set of all future edges ever revealed to the algorithm. Let bb and n,pn,p be the parameters used in the definition of the computational threshold. Future-edge algorithm conjecture. For any ϵ\epsilon, there exists a constant cϵ>0c_\epsilon>0 and an online algorithm A\mathcal{A} that finds a γ\gamma-balanced independent set of size at least (1+ϵ)αCOMP(1+\epsilon)\alpha_{\rm COMP} whp, provided

E(A(G)2)cϵlogb2(np).\left|E\cap \binom{\mathcal{A}(G)}{2}\right|\le c_\epsilon\log_b^2(np).

This conjecture asks whether limited access to future edges can allow online algorithms to exceed the computational threshold; the source presents it as an open direction and does not claim a resolution.

Sources & referencesView supporting material

Primary source

Abhishek Dhawan, Eren C. Kızıldağ and Neeladri Maitra, “Sharp Online Hardness for Large Balanced Independent Sets”, arXiv:2508.20785 (2025).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.