Authors: Coja-Oghlan, Amin
Ergür, Alperen A.
Gao, Pu
Hetterich, Samuel
Rolvien, Maurice
Title: The rank of sparse random matrices
Language (ISO): en
Abstract: 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.
Subject Headings: Finite field
Random constraint satisfaction
Random matrices
Sparse matrices
Issue Date: 2022-04-23
Rights link:
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

This item is licensed under a Creative Commons License Creative Commons