Signed low-entropy reweightings to rank one on the sphere
How much cheaper the entropy price gets once the reweighting is allowed to cancel, not just condition.
Motivation
A probability distribution over unit vectors in \(\mathbb{R}^n\) has a second moment — the average outer product of a random vector with itself — that in general looks nothing like a rank-one matrix. Reweighting the distribution before averaging can buy closeness to rank one, at a price measured in entropy (Kullback–Leibler cost, for a nonnegative reweighting). Barak, Kothari and Steurer prove that this price is exactly \(\sqrt n\) when the reweighting is required to be nonnegative — the case where reweighting means conditioning on an event — and that the bound is tight.
Their Question 8.1 asks what happens once the reweighting is allowed to go negative, so that cancellation, not just conditioning, is available. The question is not idle curiosity: the same rounding technique that answers the nonnegative case also drives the paper’s \(2^{\tilde O(\sqrt n)}\)-time algorithm for Best Separable State, and a positive answer below the square-root threshold would, by the authors’ own (hedged) account, improve both that algorithm’s running time and the best known bound on the log rank conjecture.
Provenance and history
Boaz Barak, Pravesh K. Kothari and David Steurer, Quantum entanglement, sum of squares, and the log rank conjecture, STOC 2017; arXiv:1701.06321v2, 9 July 2017. Question 8.1 is posed in Section 8 (“Conclusions and further directions”), and its nonnegative special case is Theorem 2.3, proved earlier in the paper. The statement was drafted by scripts/harvest_conjectures.py from this PDF and is AI-written and unreviewed, as the status badge says; the draft’s own adversarial check caught and corrected an unhedged claim (“would improve” for the paper’s own hedged “may improve”) before publication, verified independently against the source PDF on 19 August 2026.
The paper’s own technique traces further back: its rounding argument for Theorem 2.3 is a lift of Lovett’s proof (following Rothvoß) of the best known bound on the log rank conjecture of Lovász and Saks, embedded in the sum-of-squares proof system. Question 8.1 is the authors’ proposal for a statement general enough (not restricted to Boolean matrices) to carry that connection further.
Parameter lattice
The single free parameter is the entropy exponent \(\delta\) in the reweighting’s allowed cost \(O(n^\delta)\), crossed against whether the reweighting is allowed to be negative.
| Nonnegative \(r\) | Signed \(r\) | |
|---|---|---|
| \(\delta \ge 1/2\) | settled — Theorem 2.3, tight | implied by the nonnegative case |
| \(\delta < 1/2\) | false — the paper states the answer is No | open — tracked at c/0048 |
The paper reports no partial result for signed \(r\) at any \(\delta < 1/2\): the technique that proves Theorem 2.3 is specific to nonnegative weights, and nothing in the paper sketches how cancellation could be introduced.
Statements in this hub
- Signed low-entropy reweightings to rank one on the sphere — open for every \(\delta < 1/2\); settled and tight at \(\delta = 1/2\) with a nonnegative reweighting.