1 Search Results for "Shutty, Noah"

Document

DOI: 10.4230/LIPIcs.ITCS.2022.117

Low-Bandwidth Recovery of Linear Functions of Reed-Solomon-Encoded Data

Authors: Noah Shutty and Mary Wootters

Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)

Abstract

We study the problem of efficiently computing on encoded data. More specifically, we study the question of low-bandwidth computation of functions F:F^k → F of some data 𝐱 ∈ F^k, given access to an encoding 𝐜 ∈ Fⁿ of 𝐱 under an error correcting code. In our model - relevant in distributed storage, distributed computation and secret sharing - each symbol of 𝐜 is held by a different party, and we aim to minimize the total amount of information downloaded from each party in order to compute F(𝐱). Special cases of this problem have arisen in several domains, and we believe that it is fruitful to study this problem in generality. Our main result is a low-bandwidth scheme to compute linear functions for Reed-Solomon codes, even in the presence of erasures. More precisely, let ε > 0 and let 𝒞: F^k → Fⁿ be a full-length Reed-Solomon code of rate 1 - ε over a field F with constant characteristic. For any γ ∈ [0, ε), our scheme can compute any linear function F(𝐱) given access to any (1 - γ)-fraction of the symbols of 𝒞(𝐱), with download bandwidth O(n/(ε - γ)) bits. In contrast, the naive scheme that involves reconstructing the data 𝐱 and then computing F(𝐱) uses Θ(n log n) bits. Our scheme has applications in distributed storage, coded computation, and homomorphic secret sharing.

Cite as

Noah Shutty and Mary Wootters. Low-Bandwidth Recovery of Linear Functions of Reed-Solomon-Encoded Data. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 117:1-117:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{shutty_et_al:LIPIcs.ITCS.2022.117,
  author =	{Shutty, Noah and Wootters, Mary},
  title =	{{Low-Bandwidth Recovery of Linear Functions of Reed-Solomon-Encoded Data}},
  booktitle =	{13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
  pages =	{117:1--117:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-217-4},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{215},
  editor =	{Braverman, Mark},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.117},
  URN =		{urn:nbn:de:0030-drops-157130},
  doi =		{10.4230/LIPIcs.ITCS.2022.117},
  annote =	{Keywords: Reed-Solomon Codes, Regenerating Codes, Coded Computation}
}

Refine by Author
1 Shutty, Noah
1 Wootters, Mary

Refine by Classification
1 Mathematics of computing → Coding theory

Refine by Keyword
1 Coded Computation
1 Reed-Solomon Codes
1 Regenerating Codes

Refine by Type
1 document

Refine by Publication Year
1 2022

1 Search Results for "Shutty, Noah"

Low-Bandwidth Recovery of Linear Functions of Reed-Solomon-Encoded Data

Abstract

Cite as

Thanks for your feedback!

Could not send message