Randomized Communication Complexity for Linear Algebra Problems over Finite Fields

摘要: Finding the singularity of a matrix is basic problem in linear algebra. Chu and Schnitger [SC95] first considered this communication complexity model, which Alice holds half Bob other half. They proved that deterministic Omega(n^2 log p) for an n by over finite field F_p. Then, Clarkson Woodruff [CW09] introduced to streaming model. proposed randomized one pass algorithm uses O(k^2 n) space decide if rank k, Omega(k^2) lower bound one-way protocols We prove randomized/quantum F_p p), implies same algorithms, even constant number passes. The proof framework Lee Shraibman [LS09], but we choose Fourier coefficients as witness dual approximate norm matrix. Moreover, use analysis show when deciding determinant non-singular or b non-zero b.