{"id":"d846a738-8158-457e-8d41-01bd710a60cb","arxiv_id":"2508.20785","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"In dense random bipartite graphs, the largest gamma-balanced independent set is about log_b n/(gamma(1-gamma)), online algorithms can find only (1-epsilon)log_b n/gamma, and no online algorithm can exceed that by a constant factor.","lead":"This paper pins down the largest balanced independent sets in dense random bipartite graphs, and proves that online algorithms can only reach a fraction of the statistical maximum. It establishes a sharp factor gap that supports the conjectured universality of such statistical-computational gaps.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified","rationale":"The central hardness result, Theorem 3.5, appears sound. The reader's stated weakest assumption is the information restriction in Definition 3.2, but this restriction is exactly what makes the correlated-graph factorization work: a deterministic online algorithm's first τ steps depend only on the queried edges E_A(τ), so the common prefix is identical across the correlated graphs and the post-τ edges are conditionally independent. I verified the counting in Lemma 6.7; the probability exponent for each fixed tuple is θ_iθ'_i - β(1-μ)log_b n (all cross pairs except those inside the common I), and the crude binomial upper bounds are absorbed in the final exp(-Ω(log^2 n)) after the union bound over O(n^{O(m)}) tuples. I therefore do not see a load-bearing flaw in the OGP lower bound. However, I agree with the reader that Theorem 3.8's query accounting is problematic: the algorithm as described queries polynomially many vertex pairs to identify W_L, W_R, and to brute-force J, while the proof's final count only sums the pairs inside the output independent set. If Definition 3.7 is intended to limit the total number of queried pairs, the theorem's claimed c(γ,ε)(log_b n)^2 bound is not established. This is a real issue for the auxiliary future-query result, but it does not undermine Theorem 3.5, so the reader's conditional verdict can remain unchanged.","tokens_in":29947,"tokens_out":46234,"duration_ms":435935,"concrete_test":"Recompute the total number of vertex pairs queried in Phase II and Phase III of Theorem 3.8 by evaluating |S_{T+1}| = |I_T^(R)|·|L\\L_T|, |S_{T+2}| = |I_T^(L)|·|R\\R_{T+1}|, and |S_{T+3}| = |W_L|·|W_R|; if the sum is Ω(n^{1+o(1)}) rather than O(log^2 n), then the query-count constraint in Definition 3.7 is not met.","verdict_should_be":"UNCHANGED","load_bearing_attack":"After independent review, I find no load-bearing flaw in the proof of the central claim, Theorem 3.5. The correlated-graph argument is internally consistent: under Definition 3.2, the first τ rounds expose only edges in E_A(τ), so {τ=T} is E_A(T)-measurable, the outputs on G_i^(T) agree on V_A(T), and the conditional independence factorization in Proposition 6.3 is valid. Lemma 6.7's counting, which fixes I and I_i and multiplies (1-p)^{θ_iθ'_i - uβ} by the number of choices, correctly upper-bounds the existence of forbidden tuples; the omitted 2^{a_i} factors are dominated by the eventual exp(-Ω(log^2 n)) bound. The only substantive issue I see is in the auxiliary future-query theorem (Section 7): as written, S_{T+1}, S_{T+2}, and S_{T+3} have sizes Θ(n log n), Θ(n log n), and n^{2θ}, respectively, so the proof's final query count, which counts only pairs inside the output, does not satisfy Definition 3.7 if (3) counts all queried pairs. This does not affect Theorem 3.5.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":30044,"tokens_out":22044,"duration_ms":214575,"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":[{"comment":"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.","section":"§7 (Number of Future Queries) and Definition 3.7"}],"minor_comments":[{"comment":"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.","section":"§6.2.2, Lemma 6.7"},{"comment":"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 ω.","section":"§6.1, Lemma 6.1"},{"comment":"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.","section":"§1.2 and §3.3"},{"comment":"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.","section":"Definition 1.2"}],"recommendation":"major_revision","confidential_remarks":"The Section 7 problem is substantial but localized; the main online-hardness theorem appears sound, so I recommend major revision rather than rejection. I do not see a circularity concern: the lower bound builds on the GKW25 online-OGP framework, but the balanced bipartite application and the required correlated-graph analysis are new. The authors should also make sure the relationship with GKW25 is described precisely in the final version, since the frameworks are close."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things you should know about 2508.20785. The main result is correct: online algorithms for γ-balanced independent sets in dense G_bip(n,p) have a sharp threshold at α_COMP = log_b n / γ, and the lower bound proof holds up. The auxiliary future-query theorem is mathematically consistent but rests on a query model so permissive that the informal claims about \"limited future queries\" overstate what is actually shown. That section does not affect the main theorems.\n\nThe genuinely new material is the statistical threshold α_STAT = log_b n/(γ(1−γ)), the two-stage online algorithm achieving (1−ε)α_COMP, and the OGP-based impossibility at (1+ε)α_COMP. The two-stage design with a stopping time and truncation is a nice idea, and the correlated-graph argument adapts GKW25's online OGP framework to the bipartite balanced setting without obvious gaps. I checked the first/second moment computation and the conditioning in Proposition 6.3; both look sound. The lower bound's failure probability exp(−O(ε^2 log^2 n)) is essentially optimal. Citation pattern is honest: the reliance on GKW25 is explicit, and the balanced bipartite extension is a real addition.\n\nThe soft spot is Theorem 3.8. The reader's report and the stress-test note both suggest a query-counting inconsistency, but I think that is a misreading of Definition 3.7. The definition restricts the number of future queries that involve pairs inside the final output, not the total number of queries. The proof counts exactly those output pairs, so there is no internal contradiction. The real problem is conceptual: the model lets an online algorithm inspect a polynomial number of edges as long as few of them are in the output. That makes \"limited future queries\" a weak notion, and Theorem 3.8 is less interesting than the introduction implies. I would ask the authors to spell out this permissiveness and possibly consider a stronger constraint.\n\nThis paper is for people working on average-case hardness, OGP, and online algorithms. It deserves a serious referee. I would send it to peer review, with a request to clarify the future-query model.","headline":"The online hardness result is correct and deserves a serious referee; the future-query theorem is consistent but weaker than its informal framing suggests.","tokens_in":30688,"tokens_out":7208,"would_cite":true,"duration_ms":59379,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C80","68W27","68Q25","68Q17"],"pacs":[],"model":"deepseek-v4-flash","headline":"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…","keywords":["gamma-balanced independent sets","random bipartite graphs","online algorithms","overlap gap property","statistical-computational gap","dense random graphs","future queries"],"falsifier":"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.","tokens_in":29662,"feed_emoji":"⚖️","tokens_out":15138,"duration_ms":142095,"temperature":0.7,"pith_summary":"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.","feed_headline":"Sharp online threshold proven for balanced independent sets","feed_subtitle":"Two-stage greedy reaches the limit; no online method beats it, and limited future peeks change the game.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the refined online-OGP framework and the algorithm-dependent correlated-graph construction that the lower bound extends to the bipartite setting.","marker":"[GKW25]"},{"why":"Defines the $\\gamma$-balanced independent set problem and establishes the factor-$1/(1-\\gamma)$ gap in sparse random bipartite graphs, the benchmark transferred to the dense regime.","marker":"[PW24]"},{"why":"Introduces the overlap gap property, the geometric barrier that rules out classes of algorithms.","marker":"[GS14]"},{"why":"Introduces the multi-OGP forbidden-tuple technique that the impossibility proof adapts to $m$ correlated copies.","marker":"[RV17]"},{"why":"Gives tight low-degree hardness for maximum independent set, the contrasting algorithmic class that motivates the online model.","marker":"[Wei22]"},{"why":"Provides the dense-regime low-degree hardness result that explains why low-degree polynomial algorithms are not the right lens here.","marker":"[HS25]"}],"fun_headline_variants":["Online limit pinned for balanced independent sets","Two-stage greedy reaches exact online bound for balanced sets","Balanced independent sets: online hardness at log_b n / γ","No online algorithm beats two-stage greedy for balanced sets","Exact online threshold for balanced independent sets in dense bip graphs"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Online limit pinned for balanced independent sets","Two-stage greedy reaches exact online bound for balanced sets","Balanced independent sets: online hardness at log_b n / γ","No online algorithm beats two-stage greedy for balanced sets","Exact online threshold for balanced independent sets in dense bip graphs"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000793,"raw_usage":{"total_tokens":3599,"prompt_tokens":1156,"completion_tokens":2443,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":772,"completion_tokens_details":{"reasoning_tokens":2365}},"tokens_in":772,"tokens_out":2443,"duration_ms":16085,"temperature":1.0,"reasoning_tokens":2365,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T16:44:34.497339+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[],"review_version":2}