We determine the rank of a random matrix over an arbitrary field with prescribed numbers of non-zero entries in each row and column.
Reading the bibliography…
E. Wigner: Characteristic vectors of bordered matrices with infinite dimensions. Annals of Mathematics 62
1955
Earlier work this paper cites.
R. Gallager: Low-density parity check codes. IRE Trans. Inform. Theory 8
1962
Earlier work this paper cites.
P. Erdös, A. Rényi: On random matrices. Magyar Tud. Akad. Mat. Kutató Int. Közl. 8
1963
Earlier work this paper cites.
G. Balakin: On random matrices. Theory Probab. Appl. 12
1967
Earlier work this paper cites.
J. Komlós: On the determinant of (0,1) matrices. Studia Sci. Math. Hungar. 2
1967
Earlier work this paper cites.
I. Kovalenko: On the limit distribution of the number of solutions of a random system of linear equations in the class of Boolean functions. Theory Probab. Appl. 12
1967
Earlier work this paper cites.
G. Balakin: The distribution of random matrices over a finite field. Theory Probab. Appl. 13
1968
Earlier work this paper cites.
D. Hoover: Relations on probability spaces and arrays of random variables. Preprint, Institute of Advanced Studies, Princeton, 1979
1979
Earlier work this paper cites.
D. Aldous: Representations for partially exchangeable arrays of random variables. J. Multivariate Anal. 11
1981
Earlier work this paper cites.
A. Levitskaya: Theorems on invariance for the systems of random linear equations over an arbitrary finite ring. Soviet Math. Dokl. 263
1982
Earlier work this paper cites.
B. Bollobás: The evolution of sparse graphs. Graph theory and combinatorics (Cambridge) (1983) 35–57
1983
Earlier work this paper cites.
A. Levitskaya: The probability of consistency of a system of random linear equations over a finite ring. Theory Probab. Appl. 30
1985
Earlier work this paper cites.
I. Kovalenko, A. Levitskaya, M. Savchuk: Selected problems of probabilistic combinatorics. Naukova Dumka, Kiev (1986)
1986
Earlier work this paper cites.
V. Chvátal: Almost all graphs with 1.44 n 1.44n edges are 3-colorable. Random Structures Algorithms 2(1) (1991) 11–28
1991
Earlier work this paper cites.
T. Łuczak: Size and connectivity of the k-core of a random graph. Discrete Math., 91(1) (1991) 61–68
1991
Earlier work this paper cites.
V. Kolchin, V. Khokhlov: On the number of cycles in a random non-equiprobable graph. Discrete Math. Appl. 2
1992
Earlier work this paper cites.
T. Łuczak: Sparse random graphs with a given degree sequence. Random graphs, Vol. 2 (Poznań, 1989), Wiley-Intersci. Publ. Wiley, New York, (1992) 165–182
1992
Earlier work this paper cites.
V. Kolchin: Consistency of a system of random congruences. Discrete Math. Appl. 3
1993
Earlier work this paper cites.
J. Kahn; J. Komloś, E. Szemerédi: On the probability that a random ± 1 \pm 1 -matrix is singular. Journal of the AMS 8
1995
Earlier work this paper cites.
V. Kolchin: Random graphs and systems of linear equations in finite fields. Random Structures and Algorithms 5
1995
Earlier work this paper cites.
B. Pittel, J. Spencer, N. Wormald: Sudden emergence of a giant k k -core in a random graph. J. Combin. Theory Ser. B, 67(1) (1996) 111–151
1996
Earlier work this paper cites.
J. Blömer, R. Karp, E. Welzl: The rank of sparse random matrices over finite fields. Random Structures and Algorithms 10
1997
Earlier work this paper cites.
Y. Kabashima, D. Saad: Statistical mechanics of error correcting codes. Europhys. Lett. 45
1999
Earlier work this paper cites.
N. Wormald: Models of random regular graphs. London Mathematical Society Lecture Note Series (1999) 239–298
1999
Earlier work this paper cites.
N. Alon, J. Spencer: The probabilistic method. 2nd edition. Wiley (2000)
2000
Earlier work this paper cites.
C. Cooper: On the rank of random matrices. Random Structures and Algorithms 16
2000
Earlier work this paper cites.
S. Janson, T. Łuczak, A. Ruciński: Random graphs. Wiley (2000)
2000
Earlier work this paper cites.
B. Bollobás: Random graphs. Cambridge University Press (2001)
2001
Earlier work this paper cites.
D. Burshtein, M. Krivelevich, S. Litsyn, G. Miller: Upper bounds on the rate of LDPC codes. IEEE Transactions on Information Theory 48
2002
Earlier work this paper cites.
O. Dubois, J. Mandler: The 3-XORSAT threshold. Proc. 43rd FOCS (2002) 769–778
2002
Earlier work this paper cites.
M. Aizenman, R. Sims, S. Starr: An extended variational principle for the SK spin-glass model. Phys. Rev. B 68
2003
Cited alongside, same era.
S. Cocco, O. Dubois, J. Mandler, R. Monasson: Rigorous decimation-based construction of ground pure states for spin glass models on random lattices. Phys. Rev. Lett. 90
2003
Cited alongside, same era.
D. Fernholz, V. Ramachandran: The giant k k -core of a random graph with a specified degree sequence. Manuscript, 2003
2003
Cited alongside, same era.
S. Franz, M. Leone: Replica bounds for optimization problems and diluted spin systems. J. Stat. Phys. 111
2003
Cited alongside, same era.
F. Guerra: Broken replica symmetry bounds in the mean field spin glass model. Communications in Mathematical Physics 233
2003
Cited alongside, same era.
M. Mézard, F. Ricci-Tersenghi, R. Zecchina: Two solutions to diluted p p -spin models and XORSAT problems. Journal of Statistical Physics 111
2003
Cited alongside, same era.
G. Miller, G. Cohen: The rate of regular LDPC codes. IEEE Transactions on Information Theory 49
2003
Cited alongside, same era.
D. Aldous , M. Steele: The objective method: probabilistic combinatorial optimization and local weak convergence (2003). In: H. Kesten (ed.): Probability on discrete structures, Springer 2004
2004
Cited alongside, same era.
C. Cooper: The cores of random hypergraphs with a given degree sequence. Random Structures and Algorithms 25(4) (2004) 353–375
2004
Cited alongside, same era.
D. Fernholz, V. Ramachandran: Cores and connectivity in sparse random graphs. The University of Texas at Austin, Department of Computer Sciences, technical report TR-04-13 (2004)
2004
Cited alongside, same era.
M. Mehta: Random matrices.Academic press (2004)
2004
Cited alongside, same era.
R. Durrett: Probability theory and examples, 3rd edition (2005)
2005
Cited alongside, same era.
M. Dietzfelbinger, A. Goerdt, M. Mitzenmacher, A. Montanari, R. Pagh, M. Rink: Tight thresholds for cuckoo hashing via XORSAT. Proc. 37th ICALP (2010) 213–225
2010
Later among the works it cites.
C. Bordenave, M. Lelarge, J. Salez: The rank of diluted random graphs Ann. Probab. 39
2011
Later among the works it cites.
A. Goerdt, L. Falke: Satisfiability thresholds beyond k k -XORSAT. Proc. 7th International Computer Science Symposium in Russia (2012) 148–159
2012
Later among the works it cites.
P. Raghavendra, N. Tan: Approximating CSPs with global cardinality constraints using SDP hierarchies. Proc. 23rd SODA (2012) 373–387
2012
Later among the works it cites.
M. Bayati, D. Gamarnik, P. Tetali: Combinatorial approach to the interpolation method and scaling limits in sparse random graphs. Annals of Probability 41
2013
Later among the works it cites.
C. Bordenave, M. Lelarge, J. Salez: Matchings on infinite graphs. Probability Theory and Related Fields 157
2013
Later among the works it cites.
F. Krzakala, C. Moore, E. Mossel, J. Neeman, A. Sly, L. Zdeborová, P. Zhang: Spectral redemption in clustering sparse networks. Proc. National Academy of Sciences 110
2013
Later among the works it cites.
M. Lelarge: Bypassing correlation decay for matchings with an application to XORSAT. Proc. IEEE Information Theory Workshop (2013) 1–5
2013
Later among the works it cites.
D. Panchenko: Spin glass models from the point of view of spin distributions. Annals of Probability 41
2013
Later among the works it cites.
S. Kumar, A. Young, N. Macris, H. Pfister: Threshold saturation for spatially-coupled LDPC and LDGM Codes on BMS channels. IEEE Transactions on Information Theory 60
2014
Later among the works it cites.
V. Vu: Combinatorial problems in random matrix theory. Proc. International Congress of Mathematicians IV (2014) 489–508
2014
Later among the works it cites.
D. Achlioptas, M. Molloy: The solution space geometry of random linear equations. Random Structures and Algorithms 46
2015
Later among the works it cites.
J. Fulman, L. Goldstein: Stein’s method and the rank distribution of random matrices over finite fields. Annals of Probability 43
2015
Later among the works it cites.
M. Ibrahimi, Y. Kanoria, M. Kraning, A. Montanari: The set of solutions of random XORSAT formulae. Annals of Applied Probability 25
2015
Later among the works it cites.
V. Bapst, A. Coja-Oghlan: Harnessing the Bethe free energy. Random Structures and Algorithms 49
2016
Later among the works it cites.
A. Giurgiu, N. Macris, R. Urbanke: Spatial coupling as a proof technique and three applications. IEEE Transactions on Information Theory 62
2016
Later among the works it cites.
B. Pittel, G. Sorkin: The satisfiability threshold for k k -XORSAT. Combinatorics, Probability and Computing 25
2016
Later among the works it cites.
L. Zdeborová, F. Krzakala: Statistical physics of inference: thresholds and algorithms. Advances in Physics 65
2016
Later among the works it cites.
A. Coja-Oghlan, F. Krzakala, W. Perkins, L. Zdeborova: Information-theoretic thresholds from the cavity method. Advances in Mathematics 333
2018
Later among the works it cites.
P. Gao, M. Molloy: The stripping process can be slow: part I. Random Struct. Algorithms 53
2018
Later among the works it cites.
M. Lelarge, M. Oulamara: Replica bounds by combinatorial interpolation for diluted spin systems. Journal of Statistical Physics (2018) 1–24
2018
Later among the works it cites.
A. Coja-Oghlan, W. Perkins: Spin systems on Bethe lattices. Communications in Mathematical Physics 372
2019
Closest in time.
C. Cooper, A. Frieze, W. Pegden: On the rank of a random binary matrix. Electronic Journal of Combinatorics 26
2019
Closest in time.
P. Ayre, A. Coja-Oghlan, P. Gao, N. Müller: The satisfiability threshold for random linear equations. Combinatorica 40
2020
Closest in time.
C. Bordenave: A new proof of Friedman’s second eigenvalue Theorem and its extension to random lifts. Annales scientifiques de l’école normale supérieure 53
2020
Closest in time.
A. Dembo, E. Lubetzky, Y. Zhang: Empirical spectral distributions of sparse random graphs. In: M. Vares, R. Fernández, L. Fontes, C. Newman: In and out of equilibrium 3: Celebrating Vladas Sidoravicius (2020) 319–345
2020
Closest in time.
A. Litvak, K. Tikhomirov: Singularity of sparse Bernoulli matrices. arXiv: 2004.03131 (2020)
2020
Closest in time.
K. Tikhomirov: Singularity of random Bernoulli matrices. Annals of Mathematics 191
2020
Closest in time.
V. Jain, A. Sah, M. Sawhney: Singularity of discrete random matrices. Geometric and Functional Analysis 31
2021
Closest in time.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…