Thursday, November 28, 2019 4:00 pm
-
4:00 pm
EST (GMT -05:00)
Title: Resilience of the rank of random matrices
| Speaker: | Jorn van der Pol |
| Affiliation: | University of Waterloo |
| Room: | MC 5501 |
Abstract:
I will discuss the preprint of this title by Ferber, Luh, and McKinley (arXiv:1910.03619). An n×m-matrix M in which each entry is +1 or -1 that is chosen uniformly at random from the set of all such matrices is of full rank with high probability. In this paper it is shown that this remains true even if an adversary is allowed to change (1-ε)m/2 of the signs in M, provided that m ≥ n + n^(1-ε/6).