Autor(en): | Coja-Oghlan, Amin Ergür, Alperen A. Gao, Pu Hetterich, Samuel Rolvien, Maurice |
Titel: | The rank of sparse random matrices |
Sprache (ISO): | en |
Zusammenfassung: | We determine the asymptotic normalized rank of a random matrix A over an arbitrary field with prescribed numbers of nonzero entries in each row and column. As an application we obtain a formula for the rate of low-density parity check codes. This formula vindicates a conjecture of Lelarge (2013). The proofs are based on coupling arguments and a novel random perturbation, applicable to any matrix, that diminishes the number of short linear relations. |
Schlagwörter: | Finite field Random constraint satisfaction Random matrices Rank Sparse matrices |
URI: | http://hdl.handle.net/2003/42342 http://dx.doi.org/10.17877/DE290R-24179 |
Erscheinungsdatum: | 2022-04-23 |
Rechte (Link): | https://creativecommons.org/licenses/by/4.0/ |
Enthalten in den Sammlungen: | LS 02 Komplexitätstheorie und Effiziente Algorithmen |
Dateien zu dieser Ressource:
Datei | Beschreibung | Größe | Format | |
---|---|---|---|---|
Random Struct Algorithms - 2022 - Coja‐Oghlan - The rank of sparse random matrices.pdf | DNB | 2.29 MB | Adobe PDF | Öffnen/Anzeigen |
Diese Ressource ist urheberrechtlich geschützt. |
Diese Ressource wurde unter folgender Copyright-Bestimmung veröffentlicht: Lizenz von Creative Commons