# Non-Binary Covering Codes
for Low-Access Computations

Vinayak Ramkumar† Netanel Raviv⋆ and Itzhak Tamo†
†Department of Electrical Engineering–Systems  Tel Aviv University  Tel Aviv
Israel
⋆Department of Computer Science and Engineering  Washington University in St.
Louis  St. Louis  MO  USA
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>Parts of this
work were done when V. Ramkumar was a visiting researcher in the Department of
Computer Science and Engineering, Washington University in St. Louis. The work
of V. Ramkumar and I. Tamo was supported by the European Research Council (ERC
grant number 852953).

###### Abstract

Given a real dataset and a computation family, we wish to encode and store the
dataset in a distributed system so that any computation from the family can be
performed by accessing a small number of nodes. In this work, we focus on the
families of linear computations where the coefficients are restricted to a
finite set of real values. For two-valued computations, a recent work
presented a scheme that gives good feasible points on the access-redundancy
tradeoff. This scheme is based on binary covering codes having a certain
closure property. In a follow-up work, this scheme was extended to all finite
coefficient sets, using a new additive-combinatorics notion called coefficient
complexity. In the present paper, we explore non-binary covering codes and
develop schemes that outperform the state-of-the-art for some coefficient
sets. We provide a more general coefficient complexity definition and show its
applicability to the access-redundancy tradeoff.

###### Index Terms:

Low-access computation, distributed systems, coded computation, covering
codes.

##  I Introduction

Distributed storage and computation allow entities with limited resources
(which we will refer to as the user) to perform computations over large
datasets. In such setups, the user first stores its data in the nodes of the
distributed system. At a later time, when the user wants to perform a
computation over this distributed data, it queries the nodes and combines
their answers to get the required computation result.

Coded computation [14, 16, 15] deals with using coding theoretic techniques to
address issues like stragglers, privacy, and error-resiliency in the
distributed system. Typically, in coded computation settings, all the nodes
storing fractions of the data are contacted to perform any computation. Such
computation tasks could lead to excessive use of system resources, and in many
cases, it is beneficial to reduce the number of nodes to be contacted
preemptively. Accessing fewer nodes allows the remaining nodes to cater to a
different computation or execute other tasks.

Therefore, given a dataset and a family of computations, the user wishes to
encode and store the dataset in a distributed system so that any computation
from this family can be performed by accessing a small number of nodes. At
storage time, the user encodes the data in a manner that will be later useful
in reducing the number of nodes to be accessed to perform any computation in
the family. Optimizing such system design gives rise to an access-redundancy
tradeoff, where a smaller access requires more redundancy in the system and
vice versa. At one end of the tradeoff, the data is stored without any
redundancy, and computations require access to all nodes (minimum storage
maximum access). At the other extreme, every possible computation result is
stored in a separate node and hence just one node needs to be accessed to
perform the computation (maximum storage minimum access). The challenge in
this line of research is to come up with coding schemes that give good
feasible intermediate points for function families of interest.

It is a well-known result that the access-redundancy tradeoff for linear
computations over finite fields is equivalent to the problem of constructing
linear codes with a small covering radius [2]. The current paper investigates
access-redundancy tradeoffs in quantized linear computations over real
numbers. Linear real-valued computations are common in many applications, in
particular as part of machine learning inference. Specifically, we focus on
linear computations with quantized coefficients over real data, i.e.,
coefficients are restricted to a predetermined set of real values (such as
$\pm 1$), and no restriction is imposed over the data.

Recently, quantized linear computations have attracted much interest due to
applications in robust, efficient, and private machine learning models [9, 7,
13, 12, 3]. The access-redundancy tradeoff for quantized linear computations
has been studied in the past. For linear computations with $\\{0,1\\}$
coefficients, binary covering codes were used in [6] to get attractive points
on the access-redundancy tradeoff. Several low-access schemes for two-valued
computations were presented in [10] using binary covering codes having a
certain closure property, and these schemes outperformed the results in [6].
More recently, a scheme was presented in [11] for general coefficient sets, in
which the storage remains identical irrespective of the coefficient set and
the access parameter scales according to a newly introduced additive-
combinatorics property called coefficient complexity.

The contributions of the current paper include the following. We propose a
general method using covering codes over $\mathbb{F}_{p}$, where $p>2$ is a
prime number, to come up with feasible points on the access-redundancy
tradeoff for coefficient sets of size $p$ whose elements are in an arithmetic
progression. For $p=3$, we construct several explicit low-access schemes by
this method, and show that they outperform the previously known results for
the common coefficient family $\\{0,\pm 1\\}$. We present a general definition
of coefficient complexity so that low-access schemes based on covering codes
over $\mathbb{F}_{p}$ can be used to come up with low-access schemes for any
finite coefficient set, thus extending a previous notion that exclusively
pertained to $\mathbb{F}_{2}$.

The rest of the paper is organized as follows. In Section II, we provide the
problem statement, give a brief overview of covering codes, and summarize
previous results. Section III presents a low-access computation scheme based
on non-binary covering codes and Section IV specializes to the $p=3$ case.

##  II Background

We begin this section by defining the access-redundancy tradeoff problem for
quantized linear computations, then give a brief introduction to covering
codes and discuss prior results.

For sets $\mathcal{A},\mathcal{B}\subseteq\mathbb{R}$ we employ the standard
set addition notation $\mathcal{A}+\mathcal{B}\triangleq\\{a+b\mid
a\in\mathcal{A},b\in\mathcal{B}\\}$. For the addition of multiple sets
$\mathcal{A}_{i}$ we use
$\operatorname*{\scalerel*{+}{\textstyle\sum}}_{i}\mathcal{A}_{i}$. All
vectors in this paper are row vectors, and $\mathbbold{1}$ is the all-ones row
vector.

###  II-A Problem Statement

Given data $\mathbf{x}\in\mathbb{R}^{k}$, it is encoded to
$\mathbf{y}\in\mathbb{R}^{n}$, and stored in a distributed system with $n$
nodes such that each node stores one $y_{i}\in\mathbb{R}$. We assume that the
encoding uses a systematic linear code, i.e., every $y_{i}$ is a linear
combination of entries of $\mathbf{x}$ and there is a node storing each
$x_{i}$ in uncoded form. Systematic encoding ensures it is possible to perform
other tasks over the same stored data. A computation family of interest
$\mathcal{F}$ is known at the encoding time. The encoding mechanism must be
such that any $f\in\mathcal{F}$ can be computed by accessing at most $\ell$
nodes, where $\ell$ is the access parameter of the system. The specific
$f\in\mathcal{F}$ to be computed is not known at the time of encoding. For a
given $k$, it is preferable to minimize both storage $n$ and access $\ell$,
but a clear tradeoff exists between these quantities.

This paper focuses on quantized linear computations over the real numbers. For
finite set $\mathcal{A}\subseteq\mathbb{R}$ (which will be referred to as the
coefficient set), we define quantized linear computation family

$\mathcal{F}_{\mathcal{A}}\triangleq\\{f(\mathbf{x})=\mathbf{w}\mathbf{x}^{\intercal}|\mathbf{w}\in\mathcal{A}^{k}\\}.$

Given a coefficient set $\mathcal{A}$, we wish to develop an
$\mathcal{A}$-protocol which includes a storage (encoding) scheme, an access
scheme that identifies $\ell$ nodes to be contacted for computing a given
$f\in\mathcal{F}_{\mathcal{A}}$, and a method to combine their responses to
obtain $f(\mathbf{x})$. To understand the relation between $n,k$, and $\ell$
of $\mathcal{A}$-protocols, we focus on the redundancy ratio $n/k$ and the
access ratio $\ell/k$ in the asymptotic regime. We say that the pair
$(\alpha,\beta)$ is $\mathcal{A}$-feasible if there is an infinite family of
$\mathcal{A}$-protocols having parameters $\\{(k_{i},n_{i},\ell_{i})\\}_{i\geq
0}$ (with $k_{i}$’s strictly increasing) satisfying
$\lim_{i\to\infty}(n_{i}/k_{i},\ell_{i}/k_{i})=(\alpha,\beta)$. In [11], a
protocol is called a universal protocol if the storage scheme does not depend
on the coefficient set, i.e., all possible coefficient sets can be handled
(with potentially different access ratios).

###  II-B Covering Codes

The covering radius $r$ of a code $\mathcal{C}$ of block length $m$ over an
alphabet $\Sigma$ is defined as
$r\triangleq\min\\{u\mid\cup_{\mathbf{c}\in\mathcal{C}}B_{H}(\mathbf{c},u)=\Sigma^{m}\\},$
where $B_{H}(\mathbf{c},u)$ is the Hamming ball of radius $u$ centered at
$\mathbf{c}$. Many of the best-known covering codes in the literature [2] are
obtained through a framework called amalgamated direct sum described below.
Let $\mathcal{C}_{z}^{(i)}$ be the subset of $\mathcal{C}$ containing all
codewords with $i$-th coordinate equal to $z$. The norm $N^{(i)}$ is given by
$N^{(i)}=\max_{\mathbf{v}\in\Sigma^{n}}\left\\{\sum_{z\in\Sigma}d_{H}(\mathbf{v},\mathcal{C}_{z}^{(i)})\right\\}$,
where $d_{H}$ denotes the Hamming distance and
$d_{H}(\mathbf{v},\mathcal{S})=\min_{\mathbf{s}\in\mathcal{S}}d_{H}(\mathbf{v},\mathbf{s})$.
The $i$-th coordinate of $\mathcal{C}$ is said to be acceptable, and
$\mathcal{C}$ is said to be normal, if $N^{(i)}\leq(r+1)|\Sigma|-1$ for some
$i$. Let $\mathcal{U},\mathcal{V}$ be codes over an alphabet $\Sigma$ having
lengths $m_{1},m_{2}$ and covering radii $r_{1},r_{1}$. Suppose the last
coordinate of $\mathcal{U}$ and the first coordinate of $\mathcal{V}$ are
acceptable, and $\mathcal{U}_{z}^{(m_{1})},\mathcal{V}_{z}^{(1)}$ are not
empty for all $z\in\Sigma$. It is known [8, 5, 1] that under these conditions,
the amalgamated direct sum
$\mathcal{U}\dotplus\mathcal{V}\triangleq\bigcup_{z\in\Sigma}\\{(\mathbf{u},z,\mathbf{v})\mid(\mathbf{u},z)\in\mathcal{U},(z,\mathbf{v})\in\mathcal{V}\\}$
results in a code of length $m_{1}+m_{2}-1$ and covering radius at most
$r_{1}+r_{2}$.

###  II-C Prior Results

Here we give a summary of the previously known results on access-redundancy
tradeoffs in quantized linear computations. It is shown in [6] that if there
is a code $\mathcal{C}$ over $\mathbb{F}_{2}$ of length $m$ and covering
radius $r$, then the pair $(\frac{m+|\mathcal{C}|}{m},\frac{r+1}{m})$ is
$\\{0,1\\}$-feasible. This protocol involves partitioning $\mathbf{x}$ into
small batches of size $m$ and the non-systematic symbols are obtained by
encoding each batch with a $\\{0,1\\}$-matrix whose columns are all the
codewords of $\mathcal{C}$.

This scheme was recently improved in [10] using binary codes having a certain
closure property. Let $\mathcal{C}$ be a code over $\mathbb{F}_{2}$ and define
$\hat{\mathcal{C}}$ to be a subset of $\mathcal{C}$ containing exactly one of
$\\{\mathbf{c},\mathbf{c}\oplus\mathbbold{1}\\}$ for every
$\mathbf{c}\in\mathcal{C}$; if the code $\mathcal{C}$ over $\mathbb{F}_{2}$
has length $m$ and covering radius $r$, then the pair
$(\frac{m+|\hat{\mathcal{C}}|}{m},\frac{r+1}{m})$ is $\\{\pm 1\\}$-feasible.
The columns of the $\\{\pm 1\\}$-matrix used for encoding correspond to all
the codewords that belong to $\hat{\mathcal{C}}$. If the binary code
$\mathcal{C}$ is closed under complement (i.e., $\mathbf{c}\in\mathcal{C}$ if
and only if $\mathbf{c}\oplus\mathbbold{1}\in\mathcal{C}$), then
$|\hat{\mathcal{C}}|=|\mathcal{C}|/2$. Codes that are closed under complement
thus result in savings of almost half the storage cost and this is the crux of
the improvement in [10]. Several low-access are obtained in [10] by
constructing binary covering codes having this closure property. Additionally,
it is shown that all two-valued computations have identical feasible pairs.

More recently [11], a universal protocol was presented based on a new
additive-combinatorics notion. For any finite set
$\mathcal{A}\subset\mathbb{R}$, the complexity of $\mathcal{A}$, denoted
$C(\mathcal{A})$, is the smallest positive integer $\theta$ such that there
exists $2\theta$ real numbers $a_{1},\dots,a_{\theta},b_{1},\dots,b_{\theta}$
(not necessarily distinct) satisfying
$\mathcal{A}\subseteq\operatorname*{\scalerel*{+}{\textstyle\sum}}_{i=1}^{\theta}\\{a_{i},b_{i}\\}.$
If there exists an $\\{\pm 1\\}$-protocol which gives feasible pairs
$(\alpha,\beta)$, then for all finite sets $\mathcal{A}\subset\mathbb{R}$, it
is shown in [11] that $(\alpha,C(\mathcal{A})\beta)$ is $\mathcal{A}$-feasible
using the same encoding scheme.

##  III Schemes based on Non-Binary Codes

As discussed previously, the protocols in [10] were based on binary covering
codes. In this work, we explore the possibility of getting better feasible
pairs using non-binary codes. The following result is a direct consequence of
the definition of covering radius; nevertheless, we provide a proof for
completeness.

######  Theorem 1.

If there exists a (not necessarily linear) code $\mathcal{C}$ of length $m$
and covering radius $r$ over an alphabet $\Sigma$, then the pair
$(\frac{m+|\mathcal{C}|}{m},\frac{r+1}{m})$ is $\mathcal{A}$-feasible, where
$\mathcal{A}\subset\mathbb{R}$ is any set of size $|\Sigma|$.

###### Proof.

Let $\Sigma=\\{s_{1},\dots,s_{p}\\}$ and
$\mathcal{A}=\\{a_{1},\dots,a_{p}\\}$. Consider the representation
$s_{i}\mapsto a_{i}$ for all $i\in[p]$. Let
$B\in\mathcal{A}^{m\times|\mathcal{C}|}$ be the matrix whose columns are all
codewords of $\mathcal{C}$ in the above representation. Construct the
$m\times(m+|\mathcal{C}|)$ matrix $M=\begin{bmatrix}I\mid B\end{bmatrix}$,
where $I\in\\{0,1\\}^{m\times m}$ is the identity matrix.

Consider $k=tm$, where $t\in\mathbb{N}$. Partition
$\mathbf{x}\in\mathbb{R}^{tm}$ to $t$ parts each of size $m$, denoted by
$\mathbf{x}_{1},\ldots,\mathbf{x}_{t}$. Then, encode each part into
$\mathbf{y}_{i}=\mathbf{x}_{i}M$. Let
$\mathbf{y}=(\mathbf{y}_{1},\ldots,\mathbf{y}_{t})\in\mathbb{R}^{t(m+|\mathcal{C}|)}$
and distribute it to $n=t(m+|\mathcal{C}|)$ nodes for storage. Clearly, the
resultant redundancy ratio is $\frac{m+|\mathcal{C}|}{m}$.

The user can then compute $\mathbf{w}\mathbf{x}^{\intercal}$ for any
$\mathbf{w}\in\mathcal{A}^{k}$ as follows. Partition $\mathbf{w}$ into $t$
vectors of length $m$ each, i.e.,
$\mathbf{w}=(\mathbf{w}_{1},\ldots,\mathbf{w}_{t})$. For each $i\in[t]$, there
exists a vector $\mathbf{b}_{i}\in\mathcal{A}^{m}$ such that $\mathbf{w}_{i}$
and $\mathbf{b}_{i}$ differ on at most $r$ entries and
$\mathbf{b}_{i}^{\intercal}$ is a column of $B$. This follows since
$\mathcal{C}$ has a covering radius $r$.

To compute $\mathbf{w}_{i}\mathbf{x}_{i}^{\intercal}$, access the node storing
$\mathbf{b}_{i}\mathbf{x}_{i}^{\intercal}$ and at most $r$ nodes storing
systematic symbols $x_{i,j}$’s such that $b_{i,j}\neq w_{i,j}$. Clearly,
$\mathbf{w}_{i}\mathbf{x}_{i}^{\intercal}$ can be computed using a linear
combination of $\mathbf{b}_{i}\mathbf{x}_{i}^{\intercal}$ and those
$x_{i,j}$’s. In total, at most $t(r+1)$ nodes are accessed, leading to an
access ratio of $\frac{r+1}{m}$. ∎

The challenge is to come up with schemes that outperform the feasible pairs
given by Theorem 1, as was done for the binary case in [10] using the
aforementioned closure property. In this paper, we study schemes based on
covering codes over $\mathbb{F}_{p}$, where $p>2$ is a prime number, with a
particular focus on ternary codes. For any prime number $p>2$, let

$\mathcal{A}_{p}\triangleq\Big{\\{}0,\pm 1,\dots,\pm\frac{p-1}{2}\Big{\\}}.$

Our focus on sets of the form $\mathcal{A}_{p}$ is inspired by the commonly
used uniform quantization [4], which results in coefficient sets whose
elements are in arithmetic progression. Later, in Proposition 1, it will be
shown that all coefficient sets of size $p$ which form an arithmetic
progression have the same feasible pairs as $\mathcal{A}_{p}$. Furthermore,
Theorem 3 will show that protocols for $\mathcal{A}_{p}$ can be used as
building blocks for a universal protocol. Motivated by these, we now devise an
$\mathcal{A}_{p}$-protocol, which reduces the redundancy in storage by using
codes over $\mathbb{F}_{p}$ in a certain way.

To avoid confusion, we use the notation $\bar{\cdot}$ to emphasize that a
given element (scalar or vector) is over $\mathbb{F}_{p}$ (rather than over
$\mathbb{R}$). We use covering codes over

$\mathbb{F}_{p}=\\{\bar{0},\bar{1},\dots,\overline{(p-1)}\\}$

in their $\mathbb{R}$-representation defined as follows:

$\displaystyle\bar{0}$ $\displaystyle\mapsto 0,\bar{1}\mapsto
1,~{}\dots~{}\overline{\Big{(}\textstyle\frac{p-1}{2}\Big{)}}\mapsto\textstyle\frac{p-1}{2},$
$\displaystyle\overline{\Big{(}\textstyle\frac{p+1}{2}\Big{)}}$
$\displaystyle\mapsto-\textstyle\frac{p-1}{2},~{}\dots~{},\overline{(p-1)}\mapsto-1.$
(1)

In particular for $\mathbb{F}_{3}$, we have $\bar{0}\mapsto 0$,
$\bar{1}\mapsto 1$ and $\bar{2}\mapsto-1$. Consider any integer $i$ such that
$1\leq i\leq\frac{p-1}{2}$. Then, clearly $\bar{i}=-\overline{(p-i)}$ over
$\mathbb{F}_{p}$ corresponds to $i=-(-i)$ over $\mathbb{R}$. It follows that
under the above representation, the negation operation is homomorphic. This
enables reduction of storage overhead by using only one of
$\\{\pm\bar{\mathbf{c}}\\}$ for storage, for every
$\bar{\mathbf{c}}\in\mathcal{C}$, as described below.

######  Definition 1.

For a code $\mathcal{C}$ over $\mathbb{F}_{p}$, let
$\mathcal{S}\subseteq\mathcal{C}$ be all the codewords of Hamming weight at
most $1$, and let
$\tilde{\mathcal{C}}\subseteq\mathcal{C}\setminus\mathcal{S}$ which contains
exactly one of $\\{\pm\bar{\mathbf{c}}\\}$, for every
$\bar{\mathbf{c}}\in\mathcal{C}\setminus\mathcal{S}$. That is, first remove
all codewords from $\mathcal{C}$ that are of Hamming weight at most $1$. Then,
if $\\{\pm\bar{\mathbf{c}}\\}$ remain for some $\bar{\mathbf{c}}$, remove one
of them, and denote the resulting set by $\tilde{\mathcal{C}}$.

There are multiple ways of generating $\tilde{\mathcal{C}}$ from $\mathcal{C}$
which result in codes of identical sizes, and we fix one such way arbitrarily.

######  Example 1.

Consider the $[4,2]_{3}$ Hamming code $\mathcal{C}$ over $\mathbb{F}_{3}$. The
$2\times 4$ matrix below is a generator matrix of this code:

$\displaystyle\begin{pmatrix}\bar{0}&\bar{1}&\bar{1}&\bar{1}\\\
\bar{1}&\bar{0}&\bar{1}&\bar{2}\end{pmatrix}.$

This code has the following $9$ codewords:

$\displaystyle\\{\bar{0}\bar{0}\bar{0}\bar{0},\bar{1}\bar{0}\bar{1}\bar{2},\bar{2}\bar{0}\bar{2}\bar{1},\bar{0}\bar{1}\bar{1}\bar{1},\bar{1}\bar{1}\bar{2}\bar{0},\bar{2}\bar{1}\bar{0}\bar{2},\bar{0}\bar{2}\bar{2}\bar{2},\bar{1}\bar{2}\bar{0}\bar{1},\bar{2}\bar{2}\bar{1}\bar{0}\\}.$

Here $\mathcal{S}=\\{\bar{0}\bar{0}\bar{0}\bar{0}\\}$ and
$|\mathcal{C}\setminus\mathcal{S}|=8$. For every
$\bar{\mathbf{c}}\in\mathcal{C}\setminus\mathcal{S}$, we have
$-\bar{\mathbf{c}}\in\mathcal{C}\setminus\mathcal{S}$. Therefore,
$|\tilde{\mathcal{C}}|=4$. It can also be seen that this code has a covering
radius of $1$.

Based on the above definition, we state the following theorem which gives an
improvement over Theorem 1.

######  Theorem 2.

Let $p>2$ be a prime number. If there exists a (not necessarily linear) code
$\mathcal{C}$ of length $m$ and covering radius $r$ over $\mathbb{F}_{p}$,
then the pair $(\frac{m+|\tilde{\mathcal{C}}|}{m},\frac{r+1}{m})$ is
$\mathcal{A}_{p}$-feasible.

###### Proof.

Let $\tilde{c}\triangleq|\tilde{\mathcal{C}}|$, and let
$B\in\mathcal{A}_{p}^{m\times\tilde{c}}$ be the matrix whose columns are all
vectors in $\tilde{\mathcal{C}}$ in their $\mathbb{R}$-representation (III).
That is, for each $\bar{\mathbf{c}}\in\tilde{\mathcal{C}}$, the matrix $B$
contains as column the $\mathbb{R}$-representation $\mathbf{c}$ of
$\bar{\mathbf{c}}$. Construct the $m\times(m+\tilde{c})$ matrix
$M=\begin{bmatrix}I\mid B\end{bmatrix}$, where $I\in\\{0,1\\}^{m\times m}$ is
the identity matrix.

Consider $k=tm$, where $t\in\mathbb{N}$. Partition
$\mathbf{x}\in\mathbb{R}^{tm}$ into $t$ parts each of size $m$, denoted by
$\mathbf{x}_{1},\ldots,\mathbf{x}_{t}$. Then, encode each part
$\mathbf{x}_{i}$ into $\mathbf{y}_{i}=\mathbf{x}_{i}M$. Let
$\mathbf{y}=(\mathbf{y}_{1},\ldots,\mathbf{y}_{t})\in\mathbb{R}^{t(m+\tilde{c})}$
and distribute $\mathbf{y}$ to the $n=t(m+\tilde{c})$ nodes for storage. The
resultant redundancy ratio is $\frac{m+\tilde{c}}{m}$.

The user can then compute $\mathbf{w}\mathbf{x}^{\intercal}$ for any
$\mathbf{w}\in\mathcal{A}_{p}^{k}$ as follows. Partition $\mathbf{w}$ into $t$
vectors of length $m$ each, i.e.,
$\mathbf{w}=(\mathbf{w}_{1},\ldots,\mathbf{w}_{t})$. Since $\mathcal{C}$ is of
covering radius $r$, for each $i\in[t]$, there is a codeword
$\bar{\mathbf{c}}_{i}\in\mathcal{C}$ of Hamming distance at most $r$ from the
$\mathbb{F}_{p}$-representation $\bar{\mathbf{w}}_{i}$ of $\mathbf{w}_{i}$,
i.e., $d_{H}(\bar{\mathbf{c}}_{i},\bar{\mathbf{w}}_{i})\leq r$. The
$\mathbb{R}$-representation of $\bar{\mathbf{c}}_{i}$, which is denoted by
$\mathbf{c}_{i}$, thus differs from $\mathbf{w}_{i}$ on at most $r$ entries.
Define $\Delta_{i}\triangleq\\{j\in[m]\mid c_{i,j}\neq w_{i,j}\\}$, the set of
indices where $\mathbf{w}_{i}$ and $\mathbf{c}_{i}$ do not match. It follows
from the above discussion that $|\Delta_{i}|\leq r$, for all $i\in[t]$. We
consider two cases based on whether or not there is a node storing
$\mathbf{c}_{i}\mathbf{x}_{i}^{\intercal}$.

  1. (a)

If $\bar{\mathbf{c}}_{i}\in\hat{\mathcal{C}}$, then there is a node storing
$\mathbf{c}_{i}\mathbf{x}_{i}^{\intercal}$. To compute
$\mathbf{w}_{i}\mathbf{x}_{i}^{\intercal}$, the user accesses
$\mathbf{c}_{i}\mathbf{x}_{i}^{\intercal}$, and at most $r$ systematic symbols
$x_{i,j}$’s with $j\in\Delta_{i}$. Then,
$\mathbf{w}_{i}\mathbf{x}_{i}^{\intercal}$ can be computed as a linear
combination of $\mathbf{c}_{i}\mathbf{x}_{i}^{\intercal}$ and those
$x_{i,j}$’s as given below.

$\displaystyle\mathbf{c}_{i}\mathbf{x}_{i}^{\intercal}+\sum_{j\in\Delta_{i}}(w_{i,j}-c_{i,j})x_{i,j}\hskip
85.35826pt$ $\displaystyle=$
$\displaystyle\sum_{j\in\Delta_{i}}c_{i,j}x_{i,j}+\sum_{j\notin\Delta_{i}}c_{i,j}x_{i,j}+\sum_{j\in\Delta_{i}}(w_{i,j}-c_{i,j})x_{i,j}$
$\displaystyle=$
$\displaystyle\sum_{j\in[m]}w_{i,j}x_{i,j}=\mathbf{w}_{i}\mathbf{x}_{i}^{\intercal}.\hskip
113.81102pt$

  2. (b)

If $\bar{\mathbf{c}}_{i}\notin\hat{\mathcal{C}}$ then either
$w_{H}(\bar{\mathbf{c}}_{i})\leq 1$ or
$-\bar{\mathbf{c}}_{i}\in\hat{\mathcal{C}}$. In the former case, by triangle
inequality $w_{H}(\bar{\mathbf{w}}_{i})\leq r+1$ and hence
$\mathbf{w}_{i}\mathbf{x}_{i}^{\intercal}$ can be computed using at most $r+1$
systematic symbols. In the latter case, access the node storing
$-\mathbf{c}_{i}\mathbf{x}^{\intercal}$ and negate it to get
$\mathbf{c}_{i}\mathbf{x}^{\intercal}$. At most $r$ systematic nodes storing
$x_{i,j}$’s with $j\in\Delta_{i}$ also need to be accessed. Then,
$\mathbf{w}_{i}\mathbf{x}_{i}^{\intercal}$ can be computed by linear
combination of $\mathbf{c}_{i}\mathbf{x}_{i}^{\intercal}$ and those
$x_{i,j}$’s as described above.

To conclude the computation, obtain
$\mathbf{w}\mathbf{x}^{\intercal}=\sum_{i\in[t]}\mathbf{w}_{i}\mathbf{x}_{i}^{\intercal}$.
In total, at most $t(r+1)$ nodes are accessed, leading to an access ratio of
$\frac{r+1}{m}$. ∎

It can be seen that for coefficient set $\\{0,\pm 1\\}$, using the $[4,2]_{3}$
Hamming code in Example 1 as $\mathcal{C}$, Theorem 1 gives feasible pair
$(3.25,0.5)$, whereas Theorem 2 gives a better feasible pair $(2,0.5)$. The
following corollary specializes Theorem 2 to the ternary case.

######  Corollary 1.

If there exists a (not necessarily linear) code $\mathcal{C}$ of length $m$
and covering radius $r$ over $\mathbb{F}_{3}$, then the pair
$(\frac{m+|\tilde{C}|}{p},\frac{r+1}{m})$ is $\\{0,\pm 1\\}$-feasible.

In the next section, we will present feasible pairs obtained using a few
covering codes over $\mathbb{F}_{3}$ according to the above method and compare
them against known results [10, 11]. We remark that codes over larger
alphabets will lead to very large $\alpha$, which may not be practically
viable.

Next, we focus on coming up with a universal protocol that uses non-binary
covering codes as building blocks. For two-valued computations, it was shown
in [10] that the feasible pairs are identical irrespective of the coefficient
values. However, for computations that require three or more coefficients such
generality does not seem to hold in general, and yet, some restricted
generality does hold. Specifically, the proposition below shows that all
coefficient sets of size prime $p>2$ that form an arithmetic progression have
identical feasible pairs.

######  Proposition 1.

Let $p>2$ be a prime number and let $\mathcal{A}$ be a set of size $p$ such
that the elements of $\mathcal{A}$ are in an arithmetic progression. A pair
$(\alpha,\beta)$ is $\mathcal{A}$-feasible if and only if it is
$\mathcal{A}_{p}$-feasible. Furthermore, data stored using a protocol for
$\mathcal{A}_{p}$ can be used to retrieve $\mathbf{w}\mathbf{x}^{\intercal}$
for any $\mathbf{w}\in\mathcal{A}^{k}$ by using at most one additional node.

###### Proof.

Let $\mathcal{A}=\\{a_{1},\dots,a_{p}\\}$ with $a_{i+1}-a_{i}=d>0$, for all
$i\in[p-1]$. Given a protocol for $\mathcal{A}_{p}$, store $\mathbf{x}$
according to it, with an additional node containing
$\mathbbold{1}\mathbf{x}^{\intercal}$ if not already present. To compute any
given $\mathbf{w}\in\mathcal{A}^{k}$, consider
$\mathbf{w}^{\prime}\in\mathcal{A}_{p}^{k}$ defined as follows. If
$w_{j}=a_{i}$, then

$w^{\prime}_{j}\triangleq-\Big{(}\frac{p-1}{2}\Big{)}+i-1.$

Using the given $\mathcal{A}_{p}$-protocol for retrieving
$\mathbf{w}^{\prime}\mathbf{x}^{\intercal}$, and accessing
$\mathbbold{1}\mathbf{x}^{\intercal}$, the user can compute

$\displaystyle
d\cdot\mathbf{w}^{\prime}\mathbf{x}^{\intercal}+\Big{(}\frac{p-1}{2}d+a_{1}\Big{)}\cdot\mathbbold{1}\mathbf{x}^{\intercal}\hskip
56.9055pt$ $\displaystyle=$
$\displaystyle\sum_{i\in[p]}\sum_{j|w_{j}=a_{i}}\Big{(}-\Big{(}\frac{p-1}{2}\Big{)}d+(i-1)d+\frac{p-1}{2}d+a_{1}\Big{)}x_{j}$
$\displaystyle=$
$\displaystyle\sum_{i\in[p]}\sum_{j|w_{j}=a_{i}}\Big{(}(i-1)d+a_{1}\Big{)}x_{j}\hskip
93.89418pt$ $\displaystyle=$
$\displaystyle\sum_{i\in[p]}\sum_{j|w_{j}=a_{i}}a_{i}x_{j}=\mathbf{w}\mathbf{x}^{\intercal}.\hskip
119.50148pt$

In the other direction, given a protocol for $\mathcal{A}$, store $\mathbf{x}$
according to it, with an additional node containing
$\mathbbold{1}\mathbf{x}^{\intercal}$ if not already present. To compute any
given $\mathbf{w}\in\mathcal{A}_{p}^{k}$, consider
$\mathbf{w}^{\prime}\in\mathcal{A}^{k}$ defined as follows. If $w_{j}=i$, then

$w^{\prime}_{j}\triangleq a_{1}+\Big{(}\frac{p-1}{2}+i\Big{)}d.$

Note that this is equivalent to $w^{\prime}_{j}=a_{u}$, where
$u=\frac{p-1}{2}+i+1$, and hence $\mathbf{w}\in\mathcal{A}^{k}$. Using the
given $\mathcal{A}$-protocol for retrieving
$\mathbf{w}^{\prime}\mathbf{x}^{\intercal}$, and accessing
$\mathbbold{1}\mathbf{x}^{\intercal}$, the user can compute

$\displaystyle\frac{1}{d}\cdot\mathbf{w}^{\prime}\mathbf{x}^{\intercal}-\Big{(}\frac{p-1}{2}+\frac{a_{1}}{d}\Big{)}\cdot\mathbbold{1}\mathbf{x}^{\intercal}\hskip
42.67912pt$ $\displaystyle=$
$\displaystyle\sum_{i\in\mathcal{A}_{p}}\sum_{j|w_{j}=i}\Big{(}\frac{a_{1}}{d}+\frac{p-1}{2}+i-\frac{p-1}{2}-\frac{a_{1}}{d}\Big{)}x_{j}$
$\displaystyle=$
$\displaystyle\sum_{i\in\mathcal{A}_{p}}\sum_{j|w_{j}=i}ix_{j}=\mathbf{w}\mathbf{x}^{\intercal}.\hskip
91.04872pt$

At most one additional node is used for storage and access in both cases.
Since feasibility is defined in an asymptotic way, it follows that the
feasible pairs are identical for $\mathcal{A}$ and $\mathcal{A}_{p}$. The
furthermore part follows directly from the first part of the proof. ∎

Based on Proposition 1, we provide the following general definition of
coefficient complexity.

######  Definition 2.

For any finite set $\mathcal{A}\subset\mathbb{R}$ and any positive integer
$p\geq 2$, the $p$-complexity $C_{p}(\mathcal{A})$ of $\mathcal{A}$ is the
smallest positive integer $\theta$ such that there exist $\theta$ many sets
$S_{1},\dots,S_{\theta}\subset\mathbb{R}$ (not necessarily distinct)
satisfying the following:

  * •

$\mathcal{A}\subseteq\operatorname*{\scalerel*{+}{\textstyle\sum}}_{i=1}^{\theta}S_{i}$
and

  * •

$|S_{i}|=p$ and the elements of $S_{i}$ are in arithmetic progression, for all
$i\in[\theta]$.

######  Example 2.

For $\mathcal{A}=\\{0,1,2,3,4,5,6,7,8\\}$ it is clear that
$\mathcal{A}\subseteq\\{0,1,2\\}+\\{0,3,6\\}$. Since $\\{0,1,2\\}$ and
$\\{0,3,6\\}$ are arithmetic progressions of size three, it follows that
$C_{3}(\mathcal{A})=2$. For $\mathcal{A}=\\{0,1,2,3,4,5,6,7,9\\}$, we have
$\mathcal{A}\subseteq\\{0,1,2\\}+\\{0,3,6\\}+\\{0,9,18\\}$, and hence
$C_{3}(\mathcal{A})\leq 3$.

It can be easily verified that for $p=2$ Definition 2 specifies to [11, Def.
1]. Using arguments similar to those in [11], the following upper and lower
bounds can derived for $p$-complexity $C_{p}(\mathcal{A})$.

######  Lemma 1.

For all finite sets $\mathcal{A}\subset\mathbb{R}$ of size at least two, we
have $\lceil\log_{p}(|\mathcal{A}|)\rceil\leq
C_{p}(\mathcal{A})\leq|\mathcal{A}|-1$.

###### Proof.

Let $C_{p}(\mathcal{A})=\theta$. For any collection of sets
$S_{1},\dots,S_{\theta}\subset\mathbb{R}$ each of size $p$, it can be seen
that

$\left|\operatorname*{\scalerel*{+}{\textstyle\sum}}_{i=1}^{\theta}S_{i}\right|\leq
p^{\theta}.$

Therefore, $|\mathcal{A}|\leq p^{\theta}$. The lower bound follows.

To obtain the upper bound, without loss of generality, let
$\mathcal{A}=\\{a_{1},\dots,a_{M}\\}$ with $a_{1}<\dots<a_{M}$. Define $(M-1)$
many $p$-element sets in the following fashion:

$S_{i}=\\{a_{i}-a_{M}+(a_{M}-a_{i})j\mid j\in\mathbb{Z},0\leq j\leq p-1\\}$

for all $i\in[M-2]$ and

$S_{M-1}=\\{a_{M-1}+(a_{M}-a_{M-1})j\mid j\in\mathbb{Z},0\leq j\leq p-1\\}.$

Clearly, elements of $S_{i}$ are in arithmetic progression. Observe that
$a_{i}-a_{M}\in S_{i}$ for all $i\in[M-2]$ and that $a_{M}\in S_{M-1}$. Then,
for any $i\in[M-2]$, we have

$a_{i}=(a_{i}-a_{M}+a_{M})\in S_{i}+S_{M-1}.$

Since $0\in S_{i}$ for all $i\in[M-2]$, it follows that

$a_{i}\in\operatorname*{\scalerel*{+}{\textstyle\sum}}_{j=1}^{M-1}S_{j}$

for all $i\in[M-2]$. Also note that $\\{a_{M-1},a_{M}\\}\subseteq S_{M-1}$
results in

$\\{a_{M-1},a_{M}\\}\subseteq\operatorname*{\scalerel*{+}{\textstyle\sum}}_{j=1}^{M-1}S_{j}.$

Thus, we have shown that
$\mathcal{A}\subseteq\operatorname*{\scalerel*{+}{\textstyle\sum}}_{j=1}^{M-1}S_{j}$,
proving the upper bound. ∎

The following theorem establishes the usefulness of our new $p$-complexity
definition by providing a universal protocol.

######  Theorem 3.

Let $p>2$ be a prime number. If there exists an $\mathcal{A}_{p}$-protocol
with feasible pair $(\alpha,\beta)$, then $(\alpha,C_{p}(\mathcal{A})\beta)$
is $\mathcal{A}$-feasible using the same encoding scheme, for all finite sets
$\mathcal{A}\subset\mathbb{R}$.

###### Proof.

Let $C_{p}(\mathcal{A})=\theta$. By the definition of $p$-complexity, there
exists $S_{1},\dots,S_{\theta}\subset\mathbb{R}$ satisfying

$\mathcal{A}\subseteq\operatorname*{\scalerel*{+}{\textstyle\sum}}_{i=1}^{\theta}S_{i}$

such that each $S_{i}$ is a set of size $p$ whose elements form an arithmetic
progression. It follows that for given any $\mathbf{w}\in\mathcal{A}^{k}$, one
can find $\mathbf{w}^{(i)}\in S_{i}^{k}$, $i\in[\theta]$, such that

$\mathbf{w}=\sum_{i\in[\theta]}\mathbf{w}^{(i)}.$

Therefore,

$\mathbf{w}\mathbf{x}^{\intercal}=\sum_{i\in[\theta]}\mathbf{w}^{(i)}\mathbf{x}^{\intercal}.$

Given a protocol for $\mathcal{A}_{p}$, store $\mathbf{x}$ according to it,
with an additional node storing $\mathbbold{1}\mathbf{x}^{\intercal}$ if not
already present. Since every $S_{i}$ is an arithmetic progression, it follows
from the proof of Proposition 1 that for each $\mathbf{w}^{(i)}$ there exists
a $\hat{\mathbf{w}}^{(i)}\in\mathcal{A}_{p}$, such that
$\mathbf{w}^{(i)}\mathbf{x}^{\intercal}$ can be computed using
$\hat{\mathbf{w}}^{(i)}\mathbf{x}^{\intercal}$ and
$\mathbbold{1}\mathbf{x}^{\intercal}$. Therefore, the total access required
for computing $\mathbf{w}\mathbf{x}^{\intercal}$ is at most $\theta$ times the
access requirement of the given $\mathcal{A}_{p}$-protocol plus one additional
node storing $\mathbbold{1}\mathbf{x}^{\intercal}$. The statement of the
theorem follows due to the limit operation in the definition of feasible
pairs. ∎

From Lemma 1, it follows that for any coefficient set $\mathcal{A}$, the
universal protocol given by Theorem 3 has access ratio
$(|\mathcal{A}|-1)\beta$ in the worst-case. If $\mathcal{A}$ is not a set of
the highest complexity, then a smaller access ratio is possible. Hence,
further understanding of the complexity of various sets would be beneficial.
Similar to [11], it is possible to provide alternate definitions of
$p$-complexity and prove results on $p$-complexity of arithmetic and geometric
progressions. However, we do not delve into this in the current paper and it
is left as future work.

##  IV Three-valued Computations

In this section, we present explicit schemes by applying Corollary 1 to
several ternary covering codes. It is shown that the resultant $\\{0,\pm
1\\}$-feasible pairs outperform the best-known results [11, 10]. For any code
$\mathcal{C}$, we define $\tilde{c}\triangleq|\tilde{\mathcal{C}}|$, where
$\tilde{\mathcal{C}}$ is the subset of $\mathcal{C}$ given in Definition 1.

#### Entire space

The entire space $\mathcal{C}=\mathbb{F}_{3}^{i}$ is a covering code of size
$3^{i}$ and covering radius $r=0$. Clearly, $\tilde{c}=\frac{3^{i}-2i-1}{2}$
and the pair
$\left\\{\left(\frac{3^{i}-1}{2i},\frac{1}{i}\right)\right\\}_{i\geq 1}$ is
$\\{0,\pm 1\\}$-feasible.

#### Repetition code

It is readily verified that the repetition code
$\mathcal{C}=\operatorname{span}_{\mathbb{F}_{3}}\\{\bar{\mathbbold{1}}\\}\subseteq\mathbb{F}_{3}^{i}$
is a code of size $3$ and covering radius $r=\lfloor\frac{2i}{3}\rfloor$. It
also readily verified that $\tilde{c}=1$, which gives rise to the $\\{0,\pm
1\\}$-feasible pairs
$\left\\{\left(\frac{i+1}{i},\frac{1+\lfloor\frac{2i}{3}\rfloor}{i}\right)\right\\}_{i\geq
1}.$ By setting $k=i$, we get that the pair $(1,2/3)$ is $\\{0,\pm
1\\}$-feasible.

#### Hamming code

The $[4,2]_{3}$ Hamming code $\mathcal{C}$ over $\mathbb{F}_{3}$ generated by

$\displaystyle G_{\text{H}}=\begin{pmatrix}\bar{0}&\bar{1}&\bar{1}&\bar{1}\\\
\bar{1}&\bar{0}&\bar{1}&\bar{2}\end{pmatrix},$

is a code of covering radius $1$. As shown in Example 1, clearly
$\tilde{c}=4$. This gives rise to the $\\{0,\pm 1\\}$-feasible pair $(2,1/2)$.

We now use the amalgamated direct sum technique described in Section II-B to
get more feasible points. Notice that the $[4,2]_{3}$ Hamming code is not
normal, and hence cannot be amalgamated.

#### Expanded Hamming code and its amalgamations

We define the expanded Hamming code over $\mathbb{F}_{3}$ with generator
matrix

$\displaystyle
G_{\text{HE}}=\begin{pmatrix}\bar{0}&\bar{1}&\bar{1}&\bar{1}&\bar{0}\\\
\bar{1}&\bar{0}&\bar{1}&\bar{2}&\bar{0}\\\
\bar{0}&\bar{0}&\bar{0}&\bar{0}&\bar{1}\end{pmatrix}.$

The next proposition shows that the expanded Hamming code is compatible with
amalgamated direct sum.

######  Proposition 2.

The expanded Hamming code $\mathcal{C}$ has covering radius $1$. This code is
normal, with its last coordinate acceptable.

###### Proof.

To prove the covering radius claim, we need to show that for any
$\bar{\mathbf{w}}\in\mathbb{F}_{3}^{5}$, there exists
$\bar{\mathbf{c}}\in\mathcal{C}$ of Hamming distance at most $1$ from
$\bar{\mathbf{w}}$. If the last entry of $\bar{\mathbf{w}}$ is $\bar{0}$, then
there is some linear combination of the top two rows of $G_{\text{HE}}$ which
gives a codeword $\bar{\mathbf{c}}\in\mathcal{C}$ of Hamming distance at most
$1$ from $\bar{\mathbf{w}}$. This follows from the fact that the $[4,2]_{3}$
Hamming code has covering radius $1$. If the last entry of $\bar{\mathbf{w}}$
is some $\bar{a}\neq\bar{0}$, then the last row of $G_{\text{HE}}$ can be used
to match the last entry. The claim follows.

Now we prove that $\mathcal{C}$ is normal, with its last coordinate
acceptable. Let $\mathcal{H}$ be the $[4,2]_{3}$ Hamming code. Observe that
for all $\bar{a}\in\mathbb{F}_{3}$,

$\displaystyle\mathcal{C}_{\bar{a}}^{(5)}=\mathcal{H}\times\\{\bar{a}\\}.$

Since the code $\mathcal{H}$ is of covering radius $1$, it follows for any
$\bar{\mathbf{w}}\in\mathbb{F}_{3}^{5}$ that

$\displaystyle
d_{H}(\bar{\mathbf{w}},\mathcal{H}\times\\{\bar{a}\\})\leq\begin{cases}1&\mbox{if
}\bar{w}_{5}=\bar{a}\\\ 2&\mbox{else.}\end{cases}.$

Therefore,

$\displaystyle
N^{(5)}=\max_{\bar{\mathbf{w}}\in\mathbb{F}_{3}^{5}}\left\\{\sum_{\bar{a}\in\mathbb{F}_{3}}d_{H}(\bar{\mathbf{w}},\mathcal{C}_{\bar{a}}^{(i)})\right\\}\leq
5,$

which implies that $\mathcal{C}$ is normal and its last coordinate is
acceptable. ∎

Now, since the $i$-repetition code for $i\geq 1$ is normal with all
coordinates acceptable, it follows that it can be amalgamated with the
expanded Hamming code. The resulting code $\mathcal{C}_{i}$ is spanned by the
matrix

$\displaystyle\begin{pmatrix}\bar{0}&\bar{1}&\bar{1}&\bar{1}&\bar{0}^{i}\\\
\bar{1}&\bar{0}&\bar{1}&\bar{2}&\bar{0}^{i}\\\
\bar{0}&\bar{0}&\bar{0}&\bar{0}&\bar{1}^{i}\end{pmatrix},$

where $\bar{0}^{i}$ denotes $i$ occurrences of $\bar{0}$ (similarly
$\bar{1}^{i}$), and it is of length $m=i+4$, size $27$ and covering radius at
most $r=1+\lfloor\frac{2i}{3}\rfloor$. It can be verified that $\tilde{c}=12$,
which implies the $\\{0,\pm 1\\}$-feasibility of the pair
$\left\\{\left(\frac{i+16}{i+4},\frac{\lfloor\frac{2i}{3}\rfloor+2}{i+4}\right)\right\\}_{i\geq
1}.$

#### Comparison with known results

For $\mathcal{A}=\\{0,\pm 1\\}$, the best-known approach in the literature is
as follows. First construct a $\\{\pm 1\\}$-protocol using binary covering
codes as in [10]. Since $C_{2}(\\{0,\pm 1\\})=2$, the result in [11] ensures
there is a $\\{0,\pm 1\\}$-protocol with twice the access ratio of the $\\{\pm
1\\}$-protocol. It is known [11, 10] that points on the line joining two
feasible pairs are also feasible; this applies to our results as well. Fig. 1
shows the best $\\{0,\pm 1\\}$-feasible pairs given by the ternary codes in
the previous subsections. It can be readily seen that our protocols outperform
the results from [11, 10]. It follows from Proposition 1 that every
$3$-element set $\\{a,b,c\\}$ such that $(b-a)=(c-b)$ has the same feasible
pairs as $\\{0,\pm 1\\}$. Therefore, our new points outperform the best-known
results for such $3$-element sets as well.

Figure 1: The plot depicts access-redundancy tradeoff for
$\mathcal{A}=\\{0,\pm 1\\}$. The points in blue are the new solutions obtained
using ternary covering codes, whereas red is used to indicate the best-known
systematic solutions in the literature [11, 10].

Further, this also leads to better feasible pairs for some larger coefficient
sets. For instance, consider $\mathcal{A}=\\{0,1,2,3,4,5,6,7,8\\}$. As shown
in Example 2, we have $C_{3}(\mathcal{A})=2$. It can be verified that
$C_{2}(\mathcal{A})=4$. If one uses Theorem 3 and the result from [11] to get
$\mathcal{A}$-protocols, the access ratio will be double that of the
underlying $\\{0,\pm 1\\}$-protocols in both cases. Therefore, our ternary
code method will result in feasible pairs outperforming those given by [11].

## References

  * [1] Gerard Cohen, Antoine Lobstein and N Sloane  “Further results on the covering radius of codes”  In _IEEE Transactions on Information Theory_ 32.5 IEEE, 1986, pp. 680–694
  * [2] Gérard Cohen, Iiro Honkala, Simon Litsyn and Antoine Lobstein  “Covering codes”  Elsevier, 1997
  * [3] Zirui Deng, Vinayak Ramkumar, Rawad Bitar and Netanel Raviv  “Private Inference in Quantized Models”  In _arXiv preprint arXiv:2311.13686_ , 2023
  * [4] Robert G Gallager  “Principles of digital communication”  Cambridge University Press, 2008
  * [5] R Graham and NJAA Sloane  “On the covering radius of codes”  In _IEEE Transactions on Information Theory_ 31.3 IEEE, 1985, pp. 385–401
  * [6] Ching-Tien Ho, Jehoshua Bruck and Rakesh Agrawal  “Partial-sum queries in OLAP data cubes using covering codes”  In _IEEE Transactions on computers_ 47.12 IEEE, 1998, pp. 1326–1340
  * [7] Kai Jia and Martin Rinard  “Efficient exact verification of binarized neural networks”  In _Advances in neural information processing systems_ 33, 2020, pp. 1782–1795
  * [8] AC Lobstein and Gerhard JM Wee  “On normal and subnormal q-ary codes”  In _IEEE transactions on information theory_ 35.6 IEEE, 1989, pp. 1291–1295
  * [9] Zihao Qin, Hsiao-Ying Lin and Jie Shi  “Towards Demystifying Adversarial Robustness of Binarized Neural Networks”  In _International Conference on Applied Cryptography and Network Security_ , 2021, pp. 439–462  Springer
  * [10] Vinayak Ramkumar, Netanel Raviv and Itzhak Tamo  “Access-Redundancy Tradeoffs in Quantized Linear Computations”  In _2023 IEEE International Symposium on Information Theory (ISIT)_ IEEE, 2023, pp. 1967–1972
  * [11] Vinayak Ramkumar, Netanel Raviv and Itzhak Tamo  “Coefficient Complexity in Low-Access Quantized Linear Computations”  In _59th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2023_ IEEE, 2023, pp. 1–8
  * [12] Netanel Raviv, Rawad Bitar and Eitan Yaakobi  “Information Theoretic Private Inference in Quantized Models”  In _2022 IEEE International Symposium on Information Theory (ISIT)_ IEEE, 2022, pp. 1641–1646
  * [13] Netanel Raviv, Aidan Kelley, Minzhe Guo and Yevgeniy Vorobeychik  “Enhancing Robustness of Neural Networks through Fourier Stabilization”  In _International Conference on Machine Learning_ , 2021, pp. 8880–8889  PMLR
  * [14] Rashish Tandon, Qi Lei, Alexandros G. Dimakis and Nikos Karampatziakis  “Gradient Coding: Avoiding Stragglers in Distributed Learning”  In _Proceedings of the 34th International Conference on Machine Learning, ICML 2017_ 70 PMLR, 2017, pp. 3368–3376
  * [15] Qian Yu et al.  “Lagrange coded computing: Optimal design for resiliency, security, and privacy”  In _The 22nd International Conference on Artificial Intelligence and Statistics_ , 2019, pp. 1215–1225  PMLR
  * [16] Qian Yu, Mohammad Maddah-Ali and Salman Avestimehr  “Polynomial codes: an optimal design for high-dimensional coded matrix multiplication”  In _Advances in Neural Information Processing Systems_ 30, 2017