1. Eldorado
  2. Fakultäten
  3. 04 Fakultät für Informatik
  4. LS 02 Komplexitätstheorie und Effiziente Algorithmen
Full metadata record
DC FieldValueLanguage
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.identifier.urihttp://hdl.handle.net/2003/42342-
dc.identifier.urihttp://dx.doi.org/10.17877/DE290R-24179-
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.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.primaryidentifierhttps://doi.org/10.1002/rsa.21085de
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
Appears in Collections:LS 02 Komplexitätstheorie und Effiziente Algorithmen

Files in This Item:
File Description SizeFormat 
Random Struct Algorithms - 2022 - Coja‐Oghlan - The rank of sparse random matrices.pdfDNB2.29 MBAdobe PDFView/Open


This item is protected by original copyright

View License
Show simple item record


This item is licensed under a Creative Commons License Creative Commons