{"id":"75fc2d17-e8cf-439c-8529-65733fb4821e","arxiv_id":"2508.03961","paper_version":2,"verdict":"UNVERDICTED","confidence":"LOW","novelty_score":8.0,"correctness_risk":"unknown","formal_verification":"none","parameter_count":0,"one_line_summary":"A new SDP-guided Brownian-rounding technique, decoupling via affine spectral-independence, proves discrepancy O(√k) for degree-k set systems with k ≥ log² n and Õ(log^{1/4} n) for unit-norm matrices.","lead":"This math paper proves new bounds for two of the oldest open problems in combinatorial discrepancy, the Beck-Fiala and Komlós conjectures, improving results that had stood since 1998. It resolves the Beck-Fiala conjecture for large degree parameters and reduces the Komlós bound from the square root of log n to the fourth root of log n.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Unverified load-bearing premise: affine spectral-independence constraints must be feasible at every SDP re-solving step and yield a decoupling bound tight enough for the stated exponents; the corrupted text prevents auditing this.","rationale":"I agree with the reader's weakest assumption: the new technique is the crux. My stress-test adds a precise failure mode: the spectral gap underlying the affine spectral-independence constraints could degenerate, weakening the decoupling bound. Because the full text is unreadable mojibake, neither the reader nor I can audit the proof. The honest verdict remains UNVERDICTED: the claims are not verified, not refuted. I do not recommend moving to ACCEPT/REJECT without the readable body. No independent support (formalization, code, parameter-free derivation) is visible in the abstract. The proposed test would settle the concern by checking the main feasibility lemma.","tokens_in":24691,"tokens_out":8636,"duration_ms":117129,"concrete_test":"Obtain a readable copy of arXiv:2508.03961 and extract the lemma that states the affine spectral-independence constraints stay feasible while the SDP is re-solved during the Brownian motion. Concretely: (a) locate the definition of the spectrahedron used at each step; (b) verify by direct calculation on a small random instance (e.g., n=8, k=log² n) that after one Brownian increment the updated constraints admit a PSD solution with spectral gap at least the paper's required λ_min; (c) check that the decoupling lemma's row-count bound is exp(-Ω(T^2/σ^2)) with σ = O(1), not O(√log n). If any of these fails, the claimed exponents are not supported.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim—resolving Beck-Fiala for k ≥ log² n, improving Komlós to Õ(log^{1/4} n)—rests entirely on the new 'decoupling via affine spectral-independence' rounding. For these bounds to hold, three things must be true in the SDP-guided Brownian motion: (1) at every step the SDP with added affine spectral-independence constraints is feasible, (2) the constraints give a quantitative bound on the number of rows with large discrepancy, and (3) that bound has the correct exponent (e.g., strong enough to yield O(√k) rather than O(k^{3/4})). The abstract does not state these lemmas, and the available full text is corrupted mojibake, so they cannot be checked. This is the single load-bearing point: if the spectral gap degenerates during the walk, or the decoupling estimate carries an extra log factor, the final bounds collapse. This is not an accusation of error; it is an identification of the unverified premise.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper claims three discrepancy bounds: (1) for any set system on n elements with degree k >= log^2 n, a polynomial-time algorithm achieves discrepancy O(sqrt(k)), resolving the Beck-Fiala conjecture in that regime; (2) for k <= log^2 n, the bound is O~(sqrt(k) + sqrt(log n)); (3) for the Komlos problem, every m x n matrix with unit-length columns admits discrepancy O~(log^{1/4} n). These improve on Banaszczyk's O(sqrt(k log n)) and O(sqrt(log n)) bounds. The method is a discrete Brownian-motion rounding guided by an SDP augmented with 'affine spectral-independence' constraints that allegedly decouple the discrepancy evolution of different rows. The supplied full text, however, is corrupted mojibake; only the abstract and fragments are readable, so I cannot check any lemma, proof, or theorem statement beyond the abstract.","tokens_in":24807,"tokens_out":3076,"duration_ms":40708,"significance":"If the claims are correct, this is a major advance: it resolves the Beck-Fiala conjecture for all k >= log^2 n, removing a log factor from the previous best bound in that regime, and it gives the first improvement over Banaszczyk's O(sqrt(log n)) Komlos bound. The polynomial-time algorithms add further value, and the proposed 'decoupling via affine spectral-independence' technique could be of independent interest. The abstract is internally consistent and does not show circularity: the final discrepancy bounds are compared against external benchmarks, not fitted to them. However, the significance is entirely conditional: none of the proof ingredients can be audited from the submitted text, and the corrupted full text prevents any verification of the central technical claims.","major_comments":[{"comment":"The central claim rests on a load-bearing technical premise that is not verifiable from the supplied text. Specifically, the abstract says the algorithms 'add some extra affine spectral-independence constraints, which effectively decouple the evolution of discrepancies across different rows.' To prove the stated bounds, one must establish at least three things: (i) at every step of the discrete Brownian motion, the SDP with these added constraints remains feasible; (ii) the constraints yield a quantitative bound on the number of rows accumulating large discrepancy; and (iii) this bound has the correct exponent so that the final discrepancy is O(sqrt(k)) and O(log^{1/4} n), respectively. The full text is corrupted mojibake, so none of these lemmas or their proofs can be checked. This is not an accusation of error, but the absence of auditable evidence is decisive for my recommendation.","section":"Abstract"},{"comment":"The supplied full text is unreadable: it consists almost entirely of mojibake characters. I cannot locate the main theorems, definitions of affine spectral independence, SDP formulations, or the analysis of the Brownian-motion process. In a normal review I would cite specific sections and equations; here no section number can be trusted because the text cannot be parsed. The manuscript therefore does not currently provide the evidence needed to support its abstract-level claims.","section":"Full text (all sections)"}],"minor_comments":[{"comment":"The full text contains an inserted header 'arXiv:2508.03963v4 [cs.AI] 24 Apr 2026', which is inconsistent with the claimed paper identifier (arXiv:2508.03961) and subject classification (math.CO). This metadata mismatch should be corrected; more importantly, it underscores that the submitted file is not in a reliable state.","section":"Full text header"},{"comment":"The phrase 'resolve the Beck-Fiala Conjecture for k >= log^2 n' is potentially misleading if read in isolation. The conjecture is about all k; the paper resolves it only in the high-degree regime. The sentence is already qualified, but explicit wording such as 'resolve the conjecture in this regime' would be clearer.","section":"Abstract"},{"comment":"The notation O~(.) is defined as hiding poly(log log n) factors. This is nonstandard, since O~ typically hides powers of log n. I recommend adding a sentence explaining why the definition is restricted to poly(log log n), especially because the small-k bound and the Komlos bound may have very different logarithmic dependencies.","section":"Abstract"}],"recommendation":"uncertain","confidential_remarks":"To the editor: I cannot issue a mathematical verdict because the submitted full text is corrupted and unreadable. The abstract advertises results that, if proven, would be among the most significant in discrepancy theory in years. I recommend returning the file to the authors for a clean, readable version before any substantive review. If the clean version substantiates the claims, it could be a top-tier paper; but on the present submission there is no proof text to evaluate."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"You should know this one for the claims, not for the proofs: the abstract says they resolve Beck-Fiala for k ≥ log² n (discrepancy O(√k)), give Õ(√k + √log n) for smaller k, and cut Komlós to Õ(log^{1/4} n), all with polynomial-time algorithms. If true, these are the first real progress on Komlós since Banaszczyk and the first BF-type O(√k) bound beyond the standard regime. The technique — adding affine spectral-independence constraints to an SDP-guided Brownian motion to decouple row discrepancies — is a genuine new idea that could outlive this paper.\n\nWhat I can actually evaluate is limited. The supplied full text is mojibake; I could not read a single lemma or proof. So I am reviewing from the abstract and my knowledge of the area. The claims are internally consistent, cite the right benchmark (Banaszczyk 1998), and do not contradict known lower bounds. Both authors have real track records in discrepancy; Bansal in particular has made major advances in this exact area. The small-k bound Õ(√k + √log n) is a natural interpolation, not a red flag.\n\nThe soft spot is the load-bearing premise, exactly as the stress-test note says: the proof must show that the affine spectral-independence constraints remain feasible at every step of the Brownian motion, and that they yield a decoupling bound with the right exponent. If the spectral gap degenerates or an extra log factor sneaks into the row-counting argument, the final exponents collapse. The abstract states the method but does not state the quantitative lemma, and I cannot check it from this text. That is not an accusation — it is just where any referee must focus. There is no code or formalization, which is normal for a paper like this, but it means verification depends entirely on the written proof.\n\nThe citation pattern looks honest. Self-citation is not an issue here; Banaszczyk is the correct and standard point of comparison. Nothing suggests the results are parameter-fitted to the claimed bounds.\n\nWho is this for? People working on discrepancy, SDP rounding, and constructive proofs of combinatorial existence theorems. It deserves a serious referee: the claims are important, plausible, and from credible authors. But the editor must send out a readable manuscript — the current version is unreadable. If the actual arXiv PDF is intact, send it to review and ask referees to scrutinize the feasibility and decoupling lemmas. My own verdict on the proofs is UNVERDICTED, but the work is clearly serious and worth refereeing.","headline":"Major claimed improvements on Beck-Fiala and Komlós from a new decoupling technique, but the provided text is corrupted so the load-bearing feasibility lemmas cannot be checked.","tokens_in":25431,"tokens_out":2166,"would_cite":true,"duration_ms":28865,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05D40","68W20"],"pacs":[],"model":"deepseek-v4-flash","headline":"Resolves the Beck-Fiala conjecture for degree $k \\ge \\log^2 n$, gives an $\\widetilde{O}(\\sqrt{k}+\\sqrt{\\log n})$ bound for smaller degree, and improves the Komlós discrepancy bound to $\\widetilde{O}(\\log^{1/4} n)$, all with polynomial-time","keywords":["discrepancy","Beck-Fiala conjecture","Komlós conjecture","semidefinite programming","rounding algorithms","affine spectral independence","discrete Brownian motion","set systems"],"falsifier":"Exhibit one set system with degree $k \\ge \\log^2 n$ and discrepancy $\\omega(\\sqrt{k})$, or one unit-length-column matrix with discrepancy $\\omega(\\log^{1/4} n)$; the theorems assert no such instance exists. A computational check is to implement the SDP-guided discrete Brownian motion with the affine spectral-independence constraints and run it on random matrices and set systems—the paper promises polynomial-time colorings at the stated rates, so a single violating instance would disprove the claim.","tokens_in":24472,"feed_emoji":"🎲","tokens_out":15536,"duration_ms":172771,"temperature":0.7,"pith_summary":"This paper claims to settle the Beck-Fiala conjecture whenever the degree satisfies $k \\ge \\log^2 n$: every set system on $n$ elements, with each element in at most $k$ sets, has a ±1 coloring whose largest set imbalance is $O(\\sqrt{k})$, and such a coloring can be found in polynomial time. For smaller degree it claims $\\widetilde{O}(\\sqrt{k}+\\sqrt{\\log n})$, improving the previous $O(\\sqrt{k\\log n})$ for every $k$. For the Komlós problem it claims that every $m\\times n$ matrix with unit-length columns has discrepancy $\\widetilde{O}(\\log^{1/4} n)$, improving the previous $O(\\sqrt{\\log n})$. The unifying idea is a rounding scheme: a discrete Brownian motion guided by a semidefinite program, enriched with affine spectral-independence constraints that decouple the evolution of discrepancies across rows. If correct, these results replace two long-standing benchmarks and add a general rounding technique to discrepancy theory.","feed_headline":"Beck-Fiala resolved for degree k ≥ log² n","feed_subtitle":"New SDP rounding constraints beat the old bounds and improve Komlós to Õ(log^{1/4} n).","key_machinery":"The load-bearing mechanism is the set of affine spectral-independence constraints imposed on the SDP that steers the rounding. For a distribution over ±1 colorings, spectral independence means that no coordinate has a large influence on the others; the affine version enforces this on the distribution restricted to colorings consistent with the current partial rounding. During the discrete Brownian motion the algorithm re-solves the SDP and maintains these constraints, which decouples the discrepancy evolution of different rows. This decoupling is what produces the sharp count of rows exceeding a threshold, and it is the single new tool from which all three discrepancy bounds follow.","core_discovery":"The paper's central claim is that the Beck-Fiala conjecture is true for large degree: for every set system on $n$ elements where each element lies in at most $k$ sets and $k \\ge \\log^2 n$, there is a $\\pm1$ coloring with discrepancy $O(\\sqrt{k})$, found in polynomial time. In the remaining degree range $k \\le \\log^2 n$, the claimed bound is $\\widetilde{O}(\\sqrt{k}+\\sqrt{\\log n})$, which is no worse than the previous $O(\\sqrt{k\\log n})$ and matches $O(\\sqrt{k})$ up to a $\\sqrt{\\log n}$ additive term. For Komlós, every matrix with unit-length columns is claimed to admit a $\\pm1$ signing with row sums bounded by $\\widetilde{O}(\\log^{1/4} n)$, improving $O(\\sqrt{\\log n})$. The proof runs a discr","pith_inferences":["Going beyond the paper: the remaining Beck-Fiala gap is only the additive $\\widetilde{O}(\\sqrt{\\log n})$ for $k \\le \\log^2 n$, so a sharper small-degree argument could close the conjecture entirely.","Going beyond the paper: the $1/4$ exponent in the Komlós bound may reflect a counting tradeoff rather than a barrier; pushing the same constraints is a plausible route toward $\\mathrm{poly}(\\log\\log n)$ or $O(1)$.","Going beyond the paper: the SDP-plus-spectral-independence template should transfer to other balancing problems where cross-row correlation is the obstacle, such as vector balancing in $\\ell_p$ norms or hereditary discrepancy."],"forward_implications":["Any set system with degree $k \\ge \\log^2 n$ has discrepancy $O(\\sqrt{k})$, so the Beck-Fiala conjecture is settled in the entire large-degree regime.","For $k \\le \\log^2 n$, the discrepancy is $\\widetilde{O}(\\sqrt{k}+\\sqrt{\\log n})$, which is never worse than the prior $O(\\sqrt{k\\log n})$ and is within an additive $\\widetilde{O}(\\sqrt{\\log n})$ of the conjectured $O(\\sqrt{k})$.","The Komlós bound for unit-length-column matrices drops to $\\widetilde{O}(\\log^{1/4} n)$, the first improvement over $O(\\sqrt{\\log n})$.","All of these colorings are produced by polynomial-time algorithms, making the existential bounds effective.","The affine spectral-independence decoupling is offered as a reusable rounding primitive, so the method can be carried to other SDP-based rounding problems."],"supporting_citations":[{"why":"States the target conjecture: degree-$k$ set systems have discrepancy $O(\\sqrt{k})$; the paper settles it for $k \\ge \\log^2 n$.","marker":"[Discrete Appl. Math, 1981]"},{"why":"Provides the previous $O(\\sqrt{k\\log n})$ Beck-Fiala bound and $O(\\sqrt{\\log n})$ Komlós bound that the new results improve.","marker":"[Random Struct. Algor., 1998]"}],"fun_headline_variants":["Beck-Fiala proved for k≥log²n; Komlós improved","Komlós bound cut to O~(log^{1/4} n)","New decoupling technique beats Banaszczyk bounds","Polynomial-time coloring resolves Beck-Fiala for high degree"],"cache_read_input_tokens":2816,"weakest_assumption_plain":"The load-bearing premise is that the extra constraints added to the rounding program can be maintained at every step of the discrete Brownian motion and that they really do separate the growth of different rows' discrepancies as tightly as the proof needs; if either part fails, the stated Beck-Fiala and Komlós bounds collapse.","fun_headline_variants_meta":{"raw":{"variants":["Beck-Fiala proved for k≥log²n; Komlós improved","Komlós bound cut to O~(log^{1/4} n)","New decoupling technique beats Banaszczyk bounds","Polynomial-time coloring resolves Beck-Fiala for high degree"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.002201,"raw_usage":{"total_tokens":8447,"prompt_tokens":922,"completion_tokens":7525,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":666,"completion_tokens_details":{"reasoning_tokens":7452}},"tokens_in":666,"tokens_out":7525,"duration_ms":60410,"temperature":1.0,"reasoning_tokens":7452,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T00:59:31.740384+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Exhibit one set system with degree $k \\ge \\log^2 n$ and discrepancy $\\omega(\\sqrt{k})$, or one unit-length-column matrix with discrepancy $\\omega(\\log^{1/4} n)$; the theorems assert no such instance exists. A computational check is to implement the SDP-guided discrete Brownian motion with the affine spectral-independence constraints and run it on random matrices and set systems—the paper promises polynomial-time colorings at the stated rates, so a single violating instance would disprove the claim.","supporting_citations":[],"review_version":1}