{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,21]],"date-time":"2025-10-21T15:38:40Z","timestamp":1761061120180},"reference-count":17,"publisher":"Cambridge University Press (CUP)","issue":"2","license":[{"start":{"date-parts":[[2020,8,28]],"date-time":"2020-08-28T00:00:00Z","timestamp":1598572800000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":["cambridge.org"],"crossmark-restriction":true},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2021,3]]},"abstract":"Abstract<\/jats:title>Let M<\/jats:italic> be an n<\/jats:italic> \u00d7 m<\/jats:italic> matrix of independent Rademacher (\u00b11) random variables. It is well known that if $n \\leq m$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>, then M<\/jats:italic> is of full rank with high probability. We show that this property is resilient to adversarial changes to M<\/jats:italic>. More precisely, if $m \\ge n + {n^{1 - \\varepsilon \/6}}$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>, then even after changing the sign of (1 \u2013 \u03b5<\/jats:italic>)m<\/jats:italic>\/2 entries, M<\/jats:italic> is still of full rank with high probability. Note that this is asymptotically best possible as one can easily make any two rows proportional with at most m<\/jats:italic>\/2 changes. Moreover, this theorem gives an asymptotic solution to a slightly weakened version of a conjecture made by Van Vu in [17].<\/jats:p>","DOI":"10.1017\/s0963548320000413","type":"journal-article","created":{"date-parts":[[2020,8,28]],"date-time":"2020-08-28T07:55:35Z","timestamp":1598601335000},"page":"163-174","update-policy":"http:\/\/dx.doi.org\/10.1017\/policypage","source":"Crossref","is-referenced-by-count":2,"title":["Resilience of the rank of random matrices"],"prefix":"10.1017","volume":"30","author":[{"given":"Asaf","family":"Ferber","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kyle","family":"Luh","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gweneth","family":"McKinley","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2020,8,28]]},"reference":[{"key":"S0963548320000413_ref11","doi-asserted-by":"publisher","DOI":"10.1137\/110853157"},{"key":"S0963548320000413_ref3","doi-asserted-by":"publisher","DOI":"10.1017\/fms.2019.21"},{"key":"S0963548320000413_ref12","doi-asserted-by":"publisher","DOI":"10.1016\/j.aim.2008.01.010"},{"key":"S0963548320000413_ref17","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-77200-2_13"},{"key":"S0963548320000413_ref16","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20429"},{"key":"S0963548320000413_ref14","doi-asserted-by":"publisher","DOI":"10.4007\/annals.2009.169.595"},{"key":"S0963548320000413_ref10","unstructured":"[10] Luh, K. , Meehan, S. and Nguyen, H. H. (2019) Random matrices over finite fields: methods and results. arXiv:1907.02575"},{"key":"S0963548320000413_ref8","first-page":"223","article-title":"On the probability that a random \u00b11-matrix is singular","volume":"8","author":"Kahn","year":"1995","journal-title":"J. Amer. Math. Soc."},{"key":"S0963548320000413_ref5","doi-asserted-by":"publisher","DOI":"10.1007\/BF02018403"},{"key":"S0963548320000413_ref9","unstructured":"[9] Koml\u00f3s, J. (1967) On the determinant of (0, 1) matrices. Studia Sci. Math. Hungar 2 7\u201321."},{"key":"S0963548320000413_ref1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jfa.2009.04.016"},{"key":"S0963548320000413_ref15","doi-asserted-by":"publisher","DOI":"10.4007\/annals.2020.191.2.6"},{"key":"S0963548320000413_ref4","unstructured":"[4] Ferber, A. , Jain, V. , Luh, K. and Samotij, W. (2019) On the counting problem in inverse Littlewood\u2013Offord theory. arXiv:1904.10425"},{"key":"S0963548320000413_ref6","unstructured":"[6] Jain, V. (2019) The strong circular law: a combinatorial view. arXiv:1904.11108"},{"key":"S0963548320000413_ref2","unstructured":"[2] Campos, M. , Mattos, L. , Morris, R. and Morrison, N. (2019) On the singularity of random symmetric matrices. arXiv:1904.11478"},{"key":"S0963548320000413_ref13","doi-asserted-by":"publisher","DOI":"10.1090\/S0894-0347-07-00555-3"},{"key":"S0963548320000413_ref7","unstructured":"[7] Jain, V. (2019) Approximate Spielman\u2013Teng theorems for the least singular value of random combinatorial matrices. To appear in Israel J. Math. arXiv:1904.10592"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548320000413","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,3,4]],"date-time":"2021-03-04T12:51:45Z","timestamp":1614862305000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548320000413\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,8,28]]},"references-count":17,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2021,3]]}},"alternative-id":["S0963548320000413"],"URL":"https:\/\/doi.org\/10.1017\/s0963548320000413","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,8,28]]},"assertion":[{"value":"\u00a9 The Author(s), 2020. Published by Cambridge University Press","name":"copyright","label":"Copyright","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}}]}}