The rank of sparse random matrices

Simple item page
dc.contributor.authorCoja-Oghlan, Amin
dc.contributor.authorErgür, Alperen A.
dc.contributor.authorGao, Pu
dc.contributor.authorHetterich, Samuel
dc.contributor.authorRolvien, Maurice
dc.date.accessioned2024-02-21T14:01:20Z
dc.date.available2024-02-21T14:01:20Z
dc.date.issued2022-04-23
dc.description.abstractWe 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.en
dc.identifier.urihttp://hdl.handle.net/2003/42342
dc.identifier.urihttp://dx.doi.org/10.17877/DE290R-24179
dc.language.isoende
dc.relation.ispartofseriesRandom structures & algorithms;62(1)
dc.rights.urihttps://creativecommons.org/licenses/by/4.0/de
dc.subjectFinite fielden
dc.subjectRandom constraint satisfactionen
dc.subjectRandom matricesen
dc.subjectRanken
dc.subjectSparse matricesen
dc.subject.ddc004
dc.titleThe rank of sparse random matricesen
dc.typeTextde
dc.type.publicationtypeResearchArticlede
dcterms.accessRightsopen access
eldorado.secondarypublicationtruede
eldorado.secondarypublication.primarycitationA. Coja-Oghlan, A. A. Ergür, P. Gao, S. Hetterich, M. Rolvien, The rank of sparse random matrices, Random Struct. Algorithms. 62 (2023), 68–130. https://doi.org/10.1002/rsa.21085de
eldorado.secondarypublication.primaryidentifierhttps://doi.org/10.1002/rsa.21085de

Files

Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
Random Struct Algorithms - 2022 - Coja‐Oghlan - The rank of sparse random matrices.pdf
Size:
2.23 MB
Format:
Adobe Portable Document Format
Description:
DNB
Download
License bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
license.txt
Size:
4.85 KB
Format:
Item-specific license agreed upon to submission
Description:
Download

Collections

LS 02 Komplexitätstheorie und Effiziente Algorithmen