we-solve (beta)

CS-354-A2 · revision r1 · on CS-354

Literature report on CS-354

Literature report · LLM-generated · Submitted by yuningyang19 · yuningyang19 · gpt 6.1 sol, gpt 6 astra

Literature report. The underlying work is credited to its authors. Automated screening checks form, honesty and scope, not correctness. Status at unsolvedmath.com: open. Claims here do not change the source status.

Claim: literature report

Rohatgi (2019) explicitly gives an OVC-conditional negative answer to Basu's proposed uniform general-rank exact $O(nr^2\log n)$ assignment bound. This report identifies that published answer and its input/model qualifications. It does not settle fixed rank two, give an unconditional lower bound, or claim a new theorem.

Manuscript

Contents
  1. Literature report on TOP-30003992
  2. Original contributor disclosures
  3. Who did the work
  4. Models used
  5. Thinking level / time
  6. Other LLMs
  7. Per-model versions, thinking and roles
  8. Model eligibility and verification evidence
  9. People and roles
  10. References
  11. Declarations

Literature report on TOP-30003992

**A published conditional answer to the general-rank target.** Basu's original problem [1, p. 3012] observes rank-one sorting in $O(n\log n)$, asks about rank two, and proposes $O(nr^2\log n)$ for rank $r$. The current archive statement [3] retains that ambition.

Rohatgi [2, p. 12:3] explicitly discusses Basu's question immediately before Theorem 2 and answers it negatively under the Orthogonal Vectors Conjecture (OVC). In the theorem's notation, there is a constant $c>0$ such that an $O(n^{2-\varepsilon})$ exact minimum-assignment algorithm, for some constant $\varepsilon>0$ and rank function $r(n)=\Omega(c^{\log^* n})$, would refute OVC. Thus the obstruction already occurs at a slowly growing, nonconstant rank; a uniform $O(nr^2\log n)$ bound would be truly subquadratic in that regime. Negating the weight matrix converts maximum to minimum assignment and preserves rank.

**Representation and computational scope.** Appendix A, Theorem 18, reduces bichromatic closest pair to low-rank minimum assignment using transformed, polynomially bounded integer coordinates and **squared** Euclidean costs. For transformed coordinates $a_i,b_j\in\mathbb R^D$, the identity

$$M_{ij}=\lVert a_i\rVert^2+\lVert b_j\rVert^2-2a_i^Tb_j$$

provides a factorization with $D+2$ columns. The geometric construction therefore supplies factors; this is not merely an obstruction caused by reading an arbitrary dense matrix. The appendix's proof displays a polynomial dependence on dimension, which must be retained in runtime transfers. The conclusion uses the paper's fine-grained computational assumptions and bounded-coordinate reductions. It does not establish hardness for arbitrary unit-cost operations on unrestricted reals.

The source defines assignment by its optimum **cost**. An optimizing permutation also supplies that cost by summing its selected entries with the given factors. This should be distinguished from the separate entry-query matching-output argument in CS-354-A1 [4]. That earlier exploration discusses rank-one access and rank-two coordinate sorting, but does not cite Rohatgi or record this OVC obstruction.

**Suggested archive correction.** Add Rohatgi's Theorem 2 and Appendix A as a known conditional negative answer to the uniform general-rank target, with the representation and model qualifications above. Keep the fixed-rank-two exact question separate: this theorem does not resolve it, and this report does not certify its exhaustive current literature status. The mathematical result is Rohatgi's; the contribution here is correction of the archive's literature record, with no claim of new hardness, a new algorithm, or full unconditional disproof.

Original contributor disclosures

Transcribed from the original public submission. Editor normalization changes only the structured parser representation; these original statements are preserved.

Who did the work

LLM only (people only prompted or submitted)

Models used

OpenAI GPT 6.1 Sol, OpenAI GPT 6 Astra

Thinking level / time

Mixed (specified per model below)

Other LLMs

_No response_

Per-model versions, thinking and roles

OpenAI gpt-6-astra | version: unknown (logged model identifier gpt-6-astra) | thinking: medium | time: unknown | role: original literature investigation and research material generation; separate parent context reviewed that material.

OpenAI gpt-6.1-sol | version: unknown (logged model identifier gpt-6.1-sol) | thinking: medium, then high | time: unknown | role: submission preflight at medium; source recheck, concise literature-report assembly and submission preparation at high; a separate fresh context at high independently checked this report and its cited source correspondence (not its own draft).

Model eligibility and verification evidence

The original Medium-setting work was checked by a separate, fresh OpenAI gpt-6.1-sol context at **High**, a listed qualifying model/setting. Provider, model identifier and effort were verified from that review session's own metadata; exact serving revision and time budget are unknown. The reviewer did not draft this report. No previously demonstrated multi-agent architecture is claimed.

The independent check returned **PASS for mathematical/source correspondence**: Basu's complete original question; Rohatgi's literal Theorem 2 and OVC statement; Appendix A/Theorem 18, squared costs, explicit factors and dimension overhead; maximum/minimum and cost/permutation distinctions; fixed-rank-two limitations; and the absence of this citation in the earlier archive contribution. The reviewer independently refetched the primary sources linked in References and matched their bytes to those inspected for this report. This check does not re-prove all external hardness results or certify an exhaustive literature search.

For an exact scope identifier, the reviewed Write-up text (UTF-8, from its first paragraph through its final paragraph, one final newline) has SHA-256 `0dad456a5f3ac69a9d82f8cc58317b35480ca87f6a9753d2a23b5c7986c958b1`. This field records the public review summary; raw session logs and private research notes are not submitted.

People and roles

@yuningyang19: initiated the investigation, authorized this single-topic public literature report, and requested an independent eligible-model review before submission. No human mathematical verification is claimed.

References

[1] Amitabh Basu, “Open Problem: Maximum weighted assignment problem,” in *Combinatorial Optimization*, Oberwolfach Report 50/2018, p. 3012. DOI. Used: the complete original short problem, including rank-one sorting, rank two, and the general-rank target.

[2] Dhruv Rohatgi, *Conditional Hardness of Earth Mover Distance*, APPROX/RANDOM 2019, LIPIcs 145, 12:1–12:17. DOI. Used: the OVC statement in §1.1.1, the discussion and Theorem 2 on p. 12:3, and Appendix A / Theorem 18 and its reduction. This is a source-correspondence report, not independent re-verification of every external theorem used by the paper.

[3] we-solve, TOP-30003992 problem page and official prompt, checked 19 October 2026. Used: canonical handle, statement, input-model qualification, and current contribution listing.

[4] we-solve, CS-354-A1, revision r1, 11 October 2026. Complete text checked. Used: comparison with the recorded entry-query and sorting exploration; its advertised model configuration is not evidence of review of this report.

Declarations

- [X] I have the right to publish this material under CC BY 4.0 (software Apache-2.0), and third-party material is credited.
- [X] I understand that this issue and its contents are public immediately.
- [X] Every LLM and person involved is listed, with versions or "unknown".