Explicit Valiant-rigid matrices: construct N×N matrices with rigidity N^(1+δ) at rank εN
Difficulty 79.5: open for nearly 50 years, with every structured candidate ruled out and even P^NP constructions stuck at sub-polynomial rank; just below the log-rank conjecture (80), which has a clearer combinatorial core, and above ACC⁰ lower bounds (72). Application value 6.5: the payoff is lower bounds for linear transforms such as the FFT, with algorithmic spin-offs only from rigidity upper bounds, slightly above log-rank (5.5). Leverage 47: it would settle Valiant's route to log-depth linear-circuit lower bounds and, via Razborov rigidity and Dvir–Golovnev–Weinstein, connect to communication and data-structure lower bounds, level with log-rank (48).
The problem
Name a concrete table of numbers that stays complicated however a few entries change; it would prove circuit lower bounds.
- 1Rank measures how simple a table is
- 2Rigid: changing few entries can't simplify
- 3Rigid tables imply circuit lower bounds
- 4Most tables are rigid, none can be named
- 5Open: explicit rigid table
Definition. For a matrix and , the is the minimum number of entries of that must be changed to bring its rank down to at most . Generic matrices over an infinite field have , and a counting argument gives for random matrices over a fixed finite field. So rigid matrices abound.
Built from
earlier problems → this oneThe problems this one is built from: progress or tools it needs (builds on), special cases that come first (generalizes), and weaker results on the way (implies). On the right, what builds on it.
- Start with
- Step 2
- Explicit Valiant-rigid matrices: construct N×N matrices with rigidity N^(1+δ) at rank εNThis problem
- Then
- Static data structures: an ω(log n) cell-probe lower bound for an explicit problem at linear spaceComplexity Theory · D76.5
Path to understanding
foundations → problemThe research entries this problem rests on, in the order to read them. Each links to its explainer.
- Start with
- Step 2
- Computational complexity theoryTheory · host
- Then
- Explicit Valiant-rigid matrices: construct N×N matrices with rigidity N^(1+δ) at rank εNThe problem
State of the art
The best bound for any explicit matrix over any field is Ω((N²/r) log(N/r)) (Friedman 1993; Pudlák–Rödl 1994; Shokrollahi–Spielman–Stemann 1997), which is only O(N) at rank r = εN, far below the N^{1+δ} Valiant needs. Even with an NP oracle the regime is out of reach: Alman and Chen (FOCS 2019) construct, in P^NP and for infinitely many N, matrices needing δN² changes to reach rank 2^{(log N)^{1/4−ε}}, and Bhangale, Harsha, Paradise and Tal (arXiv:2005.03123, FOCS 2020) raise the rank to 2^{log N/Ω(log log N)} = N^{o(1)}; both are Razborov-type rigidity at sub-polynomial rank, not rank εN. Many natural candidates are known not to be Valiant-rigid: Walsh–Hadamard (Alman–Williams, arXiv:1611.05558), Fourier, circulant and Toeplitz matrices (Dvir–Liu, arXiv:1902.07334), and matrices of the form f(x AND y) and Kronecker powers of fixed matrices (Alman, arXiv:2102.11992). In the low-rank regime Alman and Liang (arXiv:2502.19580, STOC 2025) proved that the rank-(c log N) rigidity of the Walsh–Hadamard matrix over any finite field is at least N²(1/2 − N^{−c'}), with a hardness-amplification result: a slightly stronger bound at rank log^{1+ε} N would make it Razborov-rigid. Alman (arXiv:2608.06592, August 2026, preprint) then showed that changing 1% of the entries of the Walsh–Hadamard matrix over F₃ cannot bring its rank down to log² N/80, the first constant-fraction rigidity bound for an explicit family at superlogarithmic rank. All of this is far from rank εN; no explicit Valiant-rigid family is known.
Realistic applications
Mainly theoretical: it would give the first superlinear lower bounds for log-depth linear circuits (e.g. for the FFT and Walsh–Hadamard transform), and yield separations in communication complexity (Razborov rigidity). Rigidity upper bounds have already produced faster low-depth circuits for the Hadamard transform.
What counts as solved
A deterministic polynomial-time algorithm that outputs, for every N, a matrix M_N over a fixed finite field (or Q) with R_{M_N}(εN) ≥ N^{1+δ} for fixed ε, δ > 0, with a proof of the rigidity bound accepted by experts.
How it gets verified
Expert reviewOnly expert review of the argument is possible today.
A resolution is a deterministic polynomial-time construction of matrices M_N with rigidity at least N^(1+delta) at rank eps*N, plus a proof. Rigidity of a given large matrix is hard to certify by computation, and Mathlib has no rigidity theory, so algebraic-complexity experts review the proof.
Claims under verification
+ add a claimNo claimed results on the Verification board for this problem yet.
Where the work is
A new explicit construction with a proof is needed; computation only tests small candidates.
Bottlenecks
ranked by votes- #1TheoryAlgebraic structure of all natural candidates implies non-rigidity
Probabilistic-rank and polynomial-method arguments show that matrices with abelian or Kronecker structure are low-rank approximable after small perturbation, ruling out Hadamard, Fourier, circulant and AND-type matrices. Candidates must lack such symmetry while still being explicitly describable.
Community grades
Sign in to add your own grade.
Connected problems
Progress
- Aug 6, 2026Superlogarithmic-rank rigidity (preprint)source
Alman: Walsh–Hadamard over F₃ keeps rank above log² N/80 after changing 1% of entries.
- Feb 26, 2025Tight low-rank rigidity of Walsh–Hadamardsource
Alman and Liang prove rank-(c log N) rigidity N²(1/2 − N^{−c'}) and a hardness-amplification statement.
- May 6, 2020Rigid matrices from rectangular PCPssource
Bhangale, Harsha, Paradise and Tal reach rank N^{o(1)} in FNP, improving the Alman–Chen P^NP construction; still far from rank εN.
- Feb 19, 2019Fourier and circulant matrices are not rigidsource
Dvir and Liu rule out all matrices M_xy = f(x−y) over abelian groups as Valiant-rigid candidates.
- Nov 17, 2016Walsh–Hadamard is not Valiant-rigid