Pith. sign in

REVIEW 1 major objections 4 minor 5 references

Sharp Online Hardness for Large Balanced Independent Sets

T0 review · 1 major / 4 minor · reviewed 2026-08-15 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The paper pinpoints a sharp online threshold for large $\gamma$-balanced independent sets in dense random bipartite graphs: a two-stage greedy reaches $(1-\epsilon)\log_b n/\gamma$, but no online algorithm surpasses $(1+\epsilon)\log_b…

desk verdict The online hardness result is correct and deserves a serious referee; the future-query theorem is consistent but weaker than its informal framing suggests. read the letter →

arxiv 2508.20785 v2 pith:T2BAPGST submitted 2025-08-28 cs.DS cs.CCcs.DMmath.COmath.PR

Abhishek Dhawan , Eren C. K{i}z{i}ldağ , Neeladri Maitra This is my paper · ORCID
classification cs.DScs.CCcs.DMmath.COmath.PR MSC 05C8068W2768Q2568Q17
keywords gamma-balancedindependentsetsrandombipartitegraphsonlinealgorithmsoverlapgappropertystatistical-computationaldensefuturequeries
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper studies the largest $\gamma$-balanced independent set in a dense random bipartite graph $G_{\mathrm{bip}}(n,p)$, where an independent set must place a $\gamma$ fraction of its vertices on one side of the bipartition. It proves three matching statements: the statistically largest such set has size $\alpha_{\mathrm{STAT}} = \log_b n/(\gamma(1-\gamma))$ with high probability; a two-stage online greedy algorithm finds size at least $(1-\epsilon)\alpha_{\mathrm{COMP}}$ with $\alpha_{\mathrm{COMP}} = \log_b n/\gamma$; and no online algorithm, regardless of runtime, succeeds on the larger target $(1+\epsilon)\alpha_{\mathrm{COMP}}$ with probability more than $\exp(-\Omega(\epsilon^2\log_b^2 n))$. The consequence is a sharp factor-$1/(1-\gamma)$ gap between what random bipartite graphs contain and what online algorithms can provably find, the same factor that appears in the sparse setting. A sympathetic reader should care because this pins down the exact limit of a natural algorithmic model and supports the conjecture that the gap is universal across density regimes.

What carries the argument

The lower bound's engine is a family of $m=\Theta(\epsilon^{-2})$ correlated random graphs built around the algorithm itself: all $m$ graphs are identical on the edges the algorithm queries before its stopping time $\tau$, and are freshly independent afterward. The paper shows that the algorithm's success event on all $m$ graphs has probability at least $\delta^m$ by Jensen's inequality, while any $m$-tuple of large balanced independent sets is a forbidden structure appearing with probability $\exp(-\Omega(\log_b^2 n))$; the contradiction yields the threshold. The matching algorithm is a two-stage greedy with a stopping time and truncation that lets the global $\gamma$-balance constraint be enforced online, even though the algorithm sees only local, sequentially revealed information.

What would settle it

Exhibit a deterministic online algorithm on $G_{\mathrm{bip}}(n,p)$ with fixed $p$, fixed $\gamma$, and $n$ large that, for some $\epsilon>0$, outputs a $\gamma$-balanced independent set of size at least $(1+\epsilon)\log_b n/\gamma$ with probability $1/\mathrm{poly}(n)$. Such an algorithm would refute Theorem 3.5, because $1/\mathrm{poly}(n)=\exp(-O(\log n))$ exceeds the upper bound $\exp(-\Omega(\epsilon^2\log_b^2 n))$ the theorem proves.

Watch

Extended reading notes

Core claim

The central discovery is that for constant $p$ and $\gamma \in (0,1)$, the online computational threshold for $\gamma$-balanced independent sets in $G_{\mathrm{bip}}(n,p)$ is exactly $\alpha_{\mathrm{COMP}} = \log_b n/\gamma$, where $b = 1/(1-p)$. A deliberately two-stage greedy algorithm, with a stopping time in the first stage and truncation in the second, achieves $(1-\epsilon)\alpha_{\mathrm{COMP}}$ with high probability for any fixed $\epsilon>0$, while a refined overlap-gap lower bound shows that no online algorithm satisfying the information discipline of Definition 3.2 can achieve $(1+\epsilon)\alpha_{\mathrm{COMP}}$ with probability as large as $\exp(-O(\epsilon^2\log_b^2 n))$. Since the statistically largest $\gamma$-balanced set has size $\alpha_{\mathrm{STAT}} = \log_b n/(\gamma(1-\gamma))$, online algorithms fall short by exactly the factor $1/(1-\gamma)$. The lower bound is unconditional in the online model: it does not assume any complexity conjecture, only that decisions are irrevocable and based on edges incident to vertices already revealed.

Load-bearing premise

The hardness result rests on the premise that an online algorithm's decisions use only edges incident to vertices already revealed, never edges it has not queried yet; allowing it to peek at $O(\log_b^2 n)$ unqueried edges removes the barrier.

Editorial extensions

If this is right

  • For $\gamma=1/2$, the gap is a factor 2: online algorithms cannot find balanced independent sets larger than about $2\log_b n$, while balanced sets of size about $4\log_b n$ exist with high probability.
  • The lower bound is unconditional in the online model: it rules out algorithms of arbitrary computational power that obey the definition's information discipline.
  • Granting the algorithm $O(\log_b^2 n)$ future edge queries breaks the barrier: a three-phase online algorithm with limited future peeks reaches $(1+\epsilon)\alpha_{\mathrm{COMP}}$ with high probability, at quasi-polynomial cost.
  • Any online algorithm that surpasses $\alpha_{\mathrm{COMP}}$ must depend on the vertex arrival order; the paper shows that order-oblivious online algorithms are ruled out above the threshold.
  • The failure probability in the hard regime is essentially optimal, matching the probability that a randomly chosen $\gamma$-balanced set of the target size is independent.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Editorial inference: the sharp dichotomy suggests that the resource separating easy from hard is not stability or locality but access to revealed information; the future-query construction locates that resource at $O(\log_b^2 n)$ edges, so the barrier has an information-theoretic character.
  • Editorial inference: one can test the universality conjecture directly by building the same two-stage greedy plus correlated-copy lower bound for dense random $r$-partite $r$-uniform hypergraphs, where the sparse-regime analog already exists.
  • Editorial inference: the paper's adversarial-arrival remark implies any algorithm beating the threshold must be order-aware; a natural extension is to quantify how much order information is needed by varying the fraction of the arrival order an algorithm may see.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

1 major / 4 minor

Summary. The paper studies γ-balanced independent sets in dense Erdős–Rényi random bipartite graphs G_bip(n,p), where an independent set is γ-balanced if a γ fraction of its vertices lie on one side. The authors prove that the largest such set has size α_STAT = log_b n / (γ(1−γ)) whp, with b = 1/(1−p). They then give a two-stage online algorithm that achieves (1−ε)α_COMP for α_COMP = (1−γ)α_STAT, and an OGP-based lower bound stating that no online algorithm in the sense of Definition 3.2 can achieve (1+ε)α_COMP with probability larger than exp(−O(ε^2 log_b^2 n)). A separate result, Theorem 3.8, claims that adding a limited number of future queries lets an algorithm surpass α_COMP.

Significance. If the main results stand, this is a valuable contribution: it extends the online-OGP framework of GKW25 to a bipartite dense random graph setting with a global balancedness constraint, and it sharpens the emerging picture of a universal factor-1/(1−γ) statistical-computational gap. The statistical threshold proof is a clean first- and second-moment computation, and the correlated-graph argument behind Theorem 3.5 is internally consistent: under Definition 3.2 the stopping event and the first τ outputs depend only on E_A(τ), so the conditional-independence factorization in Proposition 6.3 is valid, and Lemma 6.7 gives the required exp(−Ω(log^2 n)) bound. There are no fitted parameters or data-dependent constants. The main caveat is the future-query result in Section 7, whose query accounting does not match the stated definition.

major comments (1)
  1. [§7 (Number of Future Queries) and Definition 3.7] The proof of Theorem 3.8 does not satisfy the query bound in Definition 3.7 as written. In Phase II, S_{T+1} = I_T^{(R)} × (L \ L_T) and S_{T+2} = I_T^{(L)} × (R \ R_{T+1}) each have size Θ(n log n), and S_{T+3} = W_L × W_R has size n^{2θ+o(1)}; these are far larger than c(log_b n)^2. The final "Number of Future Queries" paragraph counts only pairs whose endpoints lie in the final output (|I_T^{(L)}||J_R| + |I_T^{(R)}||J_L| + |J_L||J_R|), omitting all queried pairs that are not in the independent set. If inequality (3) is meant to bound the total number of queried pairs, then Theorem 3.8 is not established. If it is meant to count only queried pairs contained in the output, the model should be redefined explicitly and the phrase "limited future queries" would be misleading. This issue is confined to Section 7 and does not affect Theorem 3.5, but Theorem 3.8 is advertised as a main result.
minor comments (4)
  1. [§6.2.2, Lemma 6.7] The quantity p(I, I_i) is called a conditional probability, but the displayed expression omits the probability that there are no edges inside I and no edges inside I_i. Since these omitted factors are all at most 1, the displayed estimate is plausibly a valid upper bound, but the proof should state explicitly that internal-edge factors are being dropped deliberately and that the sum over I is a union bound over all possible common intersections.
  2. [§6.1, Lemma 6.1] The notation in Lemma 6.1 is confusing: A(G, ω) is used for the randomized algorithm and A(G) for the deterministic algorithm A(·, ω*), while Definition 3.3 uses A(G) for the output of a possibly randomized algorithm. The proof should clarify that the deterministic algorithm is A(·, ω*) and that the existence of ω* follows by averaging over ω.
  3. [§1.2 and §3.3] The statement in Section 3.3 that no online algorithm that is fully oblivious to the arrival order can surpass (1+ε)α_COMP is asserted informally and then argued by a short example; if this is intended as a theorem it should be stated as such and proved, otherwise it should be clearly labeled as an informal remark.
  4. [Definition 1.2] The balancedness condition uses "or" between the two inequalities; since for γ < 1/2 the two conditions are not symmetric under complementation, the intended meaning should be stated as "either of the two inequalities holds." The global convention that floors and ceilings are ignored should also be stated just before it is used in Theorem 3.1 rather than in the informal summary.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the statistical threshold, online achievability, and online lower bound are each proved in-paper from the model definition; the GKW25 self-citation is methodological, not load-bearing.

full rationale

The paper's derivation chain is self-contained at every load-bearing point. Theorem 3.1 (the statistical threshold) is a standard first/second moment computation: equation (4) gives E[Z_alpha], and the variance calculation in Section 4 yields alpha_STAT = log_b n/(gamma(1-gamma)); no quantity is fitted to the algorithm's output. Theorem 3.4 does not infer alpha_COMP from the algorithm; alpha_COMP is defined in equation (2) before the algorithm is introduced, and the two-stage greedy construction is analyzed directly via Lemmas 5.1 and 5.2 with Chernoff bounds. Theorem 3.5 is the main place where a self-citation could enter, since the paper says it 'builds on' the recent GKW25 online-OGP refinement. However, the correlated graph family, the stopping time, the conditional-independence factorization (Proposition 6.3), and the forbidden-tuple counting (Lemma 6.7, Definition 6.6) are all stated and proved in the present paper, in the bipartite balanced setting; the result is not imported from GKW25, nor is any uniqueness theorem invoked to forbid alternatives. The 'no future queries' information restriction is part of the model in Definition 3.2, not a hidden identification of conclusion with premise. Theorem 3.8 is an extension that applies the already-proved Theorem 3.1 to a smaller random bipartite graph. I therefore find no self-definitional step, no fitted parameter renamed as prediction, no ansatz smuggled in via citation, and no load-bearing self-citation; the overlap with GKW25 is a methodology credit rather than a circular reduction. The Section 7 query-accounting concern noted in review is a potential correctness issue, not a circularity.

Assumptions & free parameters 0 free parameters · 3 assumptions · 0 invented entities

The central claim depends on problem parameters p, gamma, and epsilon, which are inputs rather than fitted quantities. The proof introduces constants such as m = C epsilon^{-2}, mu = epsilon^2/2, c', and theta, but these are existential proof constants chosen to make inequalities work, not parameters fitted to data. The correlated graph families in Section 6 are proof constructions, not new physical or mathematical entities claimed to exist independently.

assumptions (3)
  • domain assumption Edges of G_bip(n,p) are independent Bernoulli(p) variables.
    This is the random graph model used throughout; all first and second moment computations in Section 4 and all coupling arguments in Section 5 rely on edge independence.
  • standard math Standard probabilistic tools: first and second moment method, Paley-Zygmund, Chernoff bounds, stochastic domination.
    Invoked in Section 4 for Theorem 3.1, in Lemmas 5.1 and 5.2, and in Lemmas 7.1 and 7.2. These are accepted background results.
  • domain assumption Validity of the overlapping gap property framework for online algorithms as developed in GKW25.
    Section 6 imports the correlated random graph family construction and the online OGP interpolation idea from GKW25. The lower bound proof is not self-contained with respect to that framework, and one of the current authors is also an author of GKW25.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Sharp Online Hardness for Large Balanced Independent Sets." pith.science (2026). https://pith.science/paper/T2BAPGST

@misc{pith2026250820785,
  author       = {Pith},
  title        = {Pith review of: Sharp Online Hardness for Large Balanced Independent Sets},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/T2BAPGST}},
  note         = {Machine review of arXiv:2508.20785}
}
abstract

We study the algorithmic problem of finding large $\gamma$-balanced independent sets in dense random bipartite graphs; an independent set is $\gamma$-balanced if a $\gamma$ proportion of its vertices lie on one side of the bipartition. In the sparse regime, Perkins and Wang established tight bounds within the low-degree polynomial (LDP) framework, showing a factor-$1/(1-\gamma)$ statistical-computational gap via the Overlap Gap Property (OGP) framework tailored for stable algorithms. However, these techniques do not appear to extend to the dense setting. For the related large independent set problem in dense random graph, the best known algorithm is an online greedy procedure that is inherently unstable, and LDP algorithms are conjectured to fail even in the "easy" regime where greedy succeeds. We show that the largest $\gamma$-balanced independent set in dense random bipartite graphs has size $\alpha:=\frac{\log_b n}{\gamma(1-\gamma)}$ whp, where $n$ is the size of each bipartition, $p$ is the edge probability, and $b=1/(1-p)$. We design an online algorithm that achieves $(1-\epsilon)(1-\gamma)\alpha$ whp for any $\epsilon>0$. We complement this with a sharp lower bound, showing that no online algorithm can achieve $(1+\epsilon)(1-\gamma)\alpha$ with nonnegligible probability. Our results suggest that the same factor-$1/(1-\gamma)$ gap is also present in the dense setting, supporting its conjectured universality. While the classical greedy procedure on $G(n,p)$ is straightforward, our algorithm is more intricate: it proceeds in two stages, incorporating a stopping time and suitable truncation to ensure that $\gamma$-balancedness-a global constraint-is met despite operating with limited information. Our lower bound utilizes the OGP framework; we build on a recent refinement of this framework for online models and extend it to the bipartite setting.

Review history (2 revisions) →

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

5 extracted references · 1 canonical work pages

  1. [1]

    Algorithmic barriers from phase transi- tions

    [AC08] Dimitris Achlioptas and Amin Coja-Oghlan. “Algorithmic barriers from phase transi- tions”. In:2008 49th Annual IEEE Symposium on Foundations of Computer Science. IEEE. 2008, pp. 793–802 (cit. on p. 7). [AR06] Dimitris Achlioptas and Federico Ricci-Tersenghi. “On the solution-space geometry of random constraint satisfaction problems”. In:Proceedings...

    arXiv 2018

  2. [3]

    The Algorithmic Phase Transition of Randomk-SAT for Low Degree Polynomials

    Cambridge University Press. 1976, pp. 419–427 (cit. on p. 1). [BH21] Guy Bresler and Brice Huang. “The Algorithmic Phase Transition of Randomk-SAT for Low Degree Polynomials”. In:arXiv preprint arXiv:2106.02129(2021) (cit. on pp. 7, 8). [Cam89] Kathie Cameron. “Induced matchings”. In:Discrete Applied Mathematics24.1-3 (1989), pp. 97–102 (cit. on p. 7). [C...

    arXiv 2021

  3. [4]

    On the independence number of random graphs

    Kyung Moon Sa, Seoul, 2014, pp. 311–340 (cit. on p. 1). [Fri90] Alan M Frieze. “On the independence number of random graphs”. In:Discrete Math- ematics81.2 (1990), pp. 171–175 (cit. on p. 1). [FL92] Alan M Frieze and T Luczak. “On the independence and chromatic numbers of random regular graphs”. In:Journal of Combinatorial Theory, Series B54.1 (1992), pp....

    arXiv 1990

  4. [24]

    Problem List

    “Problem List”. In:Problem List of the AIM Workshop Low-degree polynomial methods in average-case complexity (organizers Sam Hopkins, Tselil Schramm, and Alex Wein). 2024 (cit. on p. 1). [RV17] Mustazee Rahman and Balint Virag. “Local algorithms for independent sets are half- optimal”. In:The Annals of Probability45.3 (2017), pp. 1543–1577 (cit. on pp. 1,...

    arXiv 2017

  5. [297]

    Schloss Dagstuhl – Leibniz-Zentrum f¨ ur Informatik, 2024, 123:1–123:20 (cit

    Leibniz International Proceedings in Informatics (LIPIcs). Schloss Dagstuhl – Leibniz-Zentrum f¨ ur Informatik, 2024, 123:1–123:20 (cit. on p. 7). 34

    work page 2024

Pith tools

Reviewed August 15, 2026 · model on record in the stance chip above.