An explicit rational Valiant-rigid matrix family
The rigidity $R_A(r)$ of $A \in \mathbb{Q}^{n \times n}$ is the least number of entries of $A$ that must be changed, to rational values, to bring its rank over $\mathbb{Q}$ down to at most $r$. Valiant introduced rigidity as a route to superlinear lower bounds for linear circuits of logarithmic depth, and Alman and Liang call families as below Valiant rigid.
Problem. Construct $\delta > 0$ and matrices $A_n \in \mathbb{Q}^{n \times n}$ such that a single deterministic algorithm, given $n$ in unary, outputs the entries of $A_n$ in binary in time polynomial in $n$, and $$R_{A_n}\!\left(\left\lfloor \frac{n}{\log \log n} \right\rfloor\right) \ge n^{1+\delta}$$ for every sufficiently large $n$, where $\log$ is the natural logarithm.
Source: Valiant (1977); stated over ℚ by OpenProblemsInNLA, after Alman and Liang (2025), who state it over a field.
Imported from github.com/ajt60gaibb/OpenProblemsInNLA.
Imported from github.com/MColbrook/AIM.
Classification
- Primary
- CO — Combinatorics
- Secondary
- NA
- Keywords
- circuit lower bounds, matrix rigidity, OpenProblemsInNLA
- Literature checked
- Oct. 2, 2026 by clemens-admin
References
@inproceedings{valiant1977,
author = {Valiant, Leslie G.},
title = {Graph-theoretic arguments in low-level complexity},
booktitle = {Mathematical Foundations of Computer Science 1977},
series = {Lecture Notes in Comput. Sci.},
volume = {53},
publisher = {Springer},
year = {1977},
pages = {162--176},
doi = {10.1007/3-540-08353-7_135},
}
@inproceedings{alman2025,
author = {Alman, Josh and Liang, Jingxun},
title = {Low Rank Matrix Rigidity: Tight Lower Bounds and Hardness Amplification},
booktitle = {Proceedings of the 57th Annual ACM Symposium on Theory of Computing (STOC 2025)},
publisher = {ACM},
year = {2025},
pages = {1383--1394},
doi = {10.1145/3717823.3718287},
}
@article{dvir2020,
author = {Dvir, Zeev and Liu, Allen},
title = {Fourier and Circulant Matrices are Not Rigid},
journal = {Theory Comput.},
volume = {16},
number = {20},
year = {2020},
pages = {1--48},
doi = {10.4086/toc.2020.v016a020},
}
@misc{openproblemsinnla-ac10,
author = {Townsend, Alex},
title = {{AC-10}: An explicit rational Valiant-rigid matrix family},
howpublished = {Open Problems in Numerical Linear Algebra, GitHub repository},
year = {2026},
url = {https://github.com/ajt60gaibb/OpenProblemsInNLA/blob/main/arithmetic-and-complexity/AC-10/README.md},
note = {Read at commit e375a6f, 2026-09-30},
}
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00070, "An explicit rational Valiant-rigid matrix family", clopen.solutions.