Sum Of Squares

The sum-of-squares semidefinite-programming hierarchy, and its use for rounding algorithms and hardness arguments.

Status	Problem	Tags
	Signed rank-one reweighting below the square root Resolved, affirmatively and more strongly than asked: every Borel probability measure on the sphere admits a signed reweighting reaching an exact (not merely \(\epsilon\)-close) nonzero rank-one second moment at entropy cost only \(O(\log n)\) – below every \(n^\delta\), for every \(\delta>0\), with the constant \(C(\epsilon,\delta)=2/(e\delta)\) independent of \(\epsilon\). Proved by an AI-driven proof harness (conjecture-harness campaign c/0048) across six revision rounds, twenty independent blind adversarial referee passes over four audited rounds, and four independent triage rulings; the load-bearing chain (Lemmas 1-4, Theorem, Corollary, Corollary B) has never had an upheld finding against it. No human has reviewed the mathematics, and nothing here is formalized in Lean. A separate concurrent session forked the same campaign at round 3 and closed the same scope-commentary gap by a different (but mathematically equivalent) edit; both branches are recorded in the campaign ledger and the fork is not yet reconciled. 6 open	Log Rank Conjecture Sum Of Squaresassumptionresearch-solved
	Best Separable State, constant completeness error Open: whether the paper’s \(2^{\tilde{O}(\sqrt{n})}\)-time algorithm for Best Separable State extends from perfect (and near-perfect, \(1-1/n\)) completeness to any constant completeness error \(c<1\). The paper conjectures the affirmative and lists this first among its open questions; no partial result at any intermediate error is reported. 5 open	Quantum Information Sum Of Squaresassumption