Existential theory of the reals → Entrywise L1 low-rank approximation Complexity open

Unsolved

Clone https://github.com/reduction-zoo/entrywise-l1-low-rank-approximation to investigate Existential theory of the reals → Entrywise L1 low-rank approximation. Read the fixed question and state. Use preparation notes, the test corpus, and verifier if present; otherwise complete Prepare before a reduction attempt. Follow the repository instructions and your AutoResearch pipeline.

Submit a solution

Why this question matters

Real-algebraic hardness would strengthen ordinary NP-hardness and identify a deeper obstruction in robust low-rank fitting.

Ordinary NP-hardness of low-rank approximation does not establish the proposed real-algebraic hardness under a strict, unweighted L1 threshold.

The reduction to construct

The source asks whether a finite existential formula of polynomial equalities and inequalities over the reals is satisfiable, using binary integer coefficients. Recovery must respect the campaign’s finite algebraic witness representation; an unsatisfiable instance returns NO-SOLUTION.

The target asks whether a binary rational matrix has a rank-bounded approximation with unweighted entrywise L1 error strictly less than a rational ε. The strict inequality is part of the question; an accepted factor witness uses the specified finite rational encoding.

Construct deterministic polynomial-time maps F and G: F sends every legal source instance to a legal target instance, and G(x,y) is a valid source output for every valid output y of F(x). Preserve the stated threshold, domain and promises. The requested complexity conclusion is ∃R-hardness for the stated target problem.

Encoding multiplication through an unweighted strict error threshold remains unresolved; a universal construction is needed.

What a complete answer must include

Give explicit construction and recovery algorithms, a general proof for every legal input and every valid target output, and polynomial runtime and encoding-size bounds. Specify finite output encodings and handle NO-SOLUTION outputs when applicable. Tests compare recovered source outputs with independent source solutions.

References

Literature checked 2026-09-15. This summarizes the archived literature search on the date above. Unpublished, unindexed and overlooked work remains outside coverage; no new novelty assessment was performed.