Samenvatting
We derive a sufficient condition for a sparse random matrix with given numbers of non-zero entries in the rows and columns having full row rank. Inspired by low-density parity check codes, the family of random matrices that we investigate is very general and encompasses both matrices over finite fields and {0,1}-matrices over the rationals. The proof combines statistical physics-inspired coupling techniques with local limit arguments.
Originele taal-2 | Engels |
---|---|
Titel | Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2023 |
Redacteuren | Nicole Megow, Adam Smith |
Uitgeverij | Schloss Dagstuhl - Leibniz-Zentrum für Informatik |
ISBN van elektronische versie | 9783959772969 |
DOI's | |
Status | Gepubliceerd - sep. 2023 |
Evenement | 26th International Conference on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2023 and the 27th International Conference on Randomization and Computation, RANDOM 2023 - Atlanta, Verenigde Staten van Amerika Duur: 11 sep. 2023 → 13 sep. 2023 |
Publicatie series
Naam | Leibniz International Proceedings in Informatics, LIPIcs |
---|---|
Volume | 275 |
ISSN van geprinte versie | 1868-8969 |
Congres
Congres | 26th International Conference on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2023 and the 27th International Conference on Randomization and Computation, RANDOM 2023 |
---|---|
Land/Regio | Verenigde Staten van Amerika |
Stad | Atlanta |
Periode | 11/09/23 → 13/09/23 |
Bibliografische nota
Publisher Copyright:© 2023 Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. All rights reserved.
Financiering
Funding Amin Coja-Oghlan: DFG CO 646/3 and DFG CO 646/5 Max Hahn-Klimroth: DFG FOR 2975 Noela Müller: NWO Gravitation grant NETWORKS-024.002.003
Financiers | Financiernummer |
---|---|
Nederlandse Organisatie voor Wetenschappelijk Onderzoek | NETWORKS-024.002.003 |