The Full Rank Condition for Sparse Random Matrices

Amin Coja-Oghlan, Jane Gao, Max Hahn-Klimroth, Joon Lee, Noela Müller, Maurice Rolvien

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

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-2Engels
TitelApproximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2023
RedacteurenNicole Megow, Adam Smith
UitgeverijSchloss Dagstuhl - Leibniz-Zentrum für Informatik
ISBN van elektronische versie9783959772969
DOI's
StatusGepubliceerd - sep. 2023
Evenement26th 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. 202313 sep. 2023

Publicatie series

NaamLeibniz International Proceedings in Informatics, LIPIcs
Volume275
ISSN van geprinte versie1868-8969

Congres

Congres26th International Conference on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2023 and the 27th International Conference on Randomization and Computation, RANDOM 2023
Land/RegioVerenigde Staten van Amerika
StadAtlanta
Periode11/09/2313/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

FinanciersFinanciernummer
Nederlandse Organisatie voor Wetenschappelijk OnderzoekNETWORKS-024.002.003

    Vingerafdruk

    Duik in de onderzoeksthema's van 'The Full Rank Condition for Sparse Random Matrices'. Samen vormen ze een unieke vingerafdruk.

    Citeer dit