1 Search Results for "Hickey, Chris"

Document
DOI: 10.4230/LIPIcs.ISAAC.2019.48
Efficient Interactive Proofs for Linear Algebra

Authors: Graham Cormode and Chris Hickey

Published in: LIPIcs, Volume 149, 30th International Symposium on Algorithms and Computation (ISAAC 2019)

Abstract
Motivated by the growth in outsourced data analysis, we describe methods for verifying basic linear algebra operations performed by a cloud service without having to recalculate the entire result. We provide novel protocols in the streaming setting for inner product, matrix multiplication and vector-matrix-vector multiplication where the number of rounds of interaction can be adjusted to tradeoff space, communication, and duration of the protocol. Previous work suggests that the costs of these interactive protocols are optimized by choosing O(log n) rounds. However, we argue that we can reduce the number of rounds without incurring a significant time penalty by considering the total end-to-end time, so fewer rounds and larger messages are preferable. We confirm this claim with an experimental study that shows that a constant number of rounds gives the fastest protocol.
Cite as

Graham Cormode and Chris Hickey. Efficient Interactive Proofs for Linear Algebra. In 30th International Symposium on Algorithms and Computation (ISAAC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 149, pp. 48:1-48:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{cormode_et_al:LIPIcs.ISAAC.2019.48,
  author =	{Cormode, Graham and Hickey, Chris},
  title =	{{Efficient Interactive Proofs for Linear Algebra}},
  booktitle =	{30th International Symposium on Algorithms and Computation (ISAAC 2019)},
  pages =	{48:1--48:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-130-6},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{149},
  editor =	{Lu, Pinyan and Zhang, Guochuan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2019.48},
  URN =		{urn:nbn:de:0030-drops-115449},
  doi =		{10.4230/LIPIcs.ISAAC.2019.48},
  annote =	{Keywords: Streaming Interactive Proofs, Linear Algebra}
}
  • Refine by Author
  • 1 Cormode, Graham
  • 1 Hickey, Chris

  • Refine by Classification
  • 1 Theory of computation → Interactive computation

  • Refine by Keyword
  • 1 Linear Algebra
  • 1 Streaming Interactive Proofs

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2019

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