Hickey, Christopher J. A. and Cormode, Graham (2019) Efficient interactive proofs for linear algebra. In: ISAAC 2019: The 30th International Symposium on Algorithms and Computation, Shanghai, China, 8-11 Dec 2019. Published in: 30th International Symposium on Algorithms and Computation (ISAAC 2019), 149 48:1-48:19. ISBN 9783959771306. doi:10.4230/LIPIcs.ISAAC.2019.48
Preview |
PDF
WRAP-Efficient-interactive-linear-algebra-Cormode-2019.pdf - Published Version - Requires a PDF viewer. Available under License Creative Commons Attribution . Download (651kB) | Preview |
![[thumbnail of WRAP-Efficient-interactive-linear-algebra-Cormode-2019.pdf]](https://wrap.warwick.ac.uk/style/images/fileicons/application_pdf.png) |
PDF
WRAP-Efficient-interactive-linear-algebra-Cormode-2019.pdf - Accepted Version Embargoed item. Restricted access to Repository staff only - Requires a PDF viewer. Download (1MB) |
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.
| Item Type: | Conference Item (Paper) |
|---|---|
| Subjects: | Q Science > QA Mathematics Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software |
| Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science |
| Library of Congress Subject Headings (LCSH): | Mathematics -- Data processing, Algebras, Linear, Algebra -- Data processing |
| Series Name: | Leibniz International Proceedings in Informatics |
| Journal or Publication Title: | 30th International Symposium on Algorithms and Computation (ISAAC 2019) |
| Publisher: | Leibniz International Proceedings in Informatics (LIPIcs) series |
| ISBN: | 9783959771306 |
| Official Date: | 24 September 2019 |
| Dates: | Date Event 24 September 2019 Accepted |
| Volume: | 149 |
| Page Range: | 48:1-48:19 |
| DOI: | 10.4230/LIPIcs.ISAAC.2019.48 |
| Status: | Peer Reviewed |
| Publication Status: | Published |
| Access rights to Published version: | Open Access (Creative Commons open licence) |
| Date of first compliant deposit: | 25 October 2019 |
| Date of first compliant Open Access: | 25 October 2019 |
| RIOXX Funder/Project Grant: | Project/Grant ID RIOXX Funder Name Funder ID |
| Conference Paper Type: | Paper |
| Title of Event: | ISAAC 2019: The 30th International Symposium on Algorithms and Computation |
| Type of Event: | Conference |
| Location of Event: | Shanghai, China |
| Date(s) of Event: | 8-11 Dec 2019 |
| Related URLs: | |
| URI: | https://wrap.warwick.ac.uk/128490/ |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |