1 Search Results for "Wang, Chengu"

Document
DOI: 10.4230/LIPIcs.STACS.2012.477
Randomized Communication Complexity for Linear Algebra Problems over Finite Fields

Authors: Xiaoming Sun and Chengu Wang

Published in: LIPIcs, Volume 14, 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)

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

Xiaoming Sun and Chengu Wang. Randomized Communication Complexity for Linear Algebra Problems over Finite Fields. In 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012). Leibniz International Proceedings in Informatics (LIPIcs), Volume 14, pp. 477-488, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@InProceedings{sun_et_al:LIPIcs.STACS.2012.477,
  author =	{Sun, Xiaoming and Wang, Chengu},
  title =	{{Randomized Communication Complexity for Linear Algebra Problems over Finite Fields}},
  booktitle =	{29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)},
  pages =	{477--488},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-35-4},
  ISSN =	{1868-8969},
  year =	{2012},
  volume =	{14},
  editor =	{D\"{u}rr, Christoph and Wilke, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2012.477},
  URN =		{urn:nbn:de:0030-drops-34385},
  doi =		{10.4230/LIPIcs.STACS.2012.477},
  annote =	{Keywords: communication complexity, streaming, matrix, singularity, determinant}
}
  • Refine by Author
  • 1 Sun, Xiaoming
  • 1 Wang, Chengu

  • Refine by Classification

  • Refine by Keyword
  • 1 communication complexity
  • 1 determinant
  • 1 matrix
  • 1 singularity
  • 1 streaming

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2012

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact