Improved Bounds on Access-Redundancy Tradeoffs in Quantized Linear Computations
Ching-Fang Li, Mary Wootters · 2025
Read Improved Bounds on Access-Redundancy Tradeoffs in Quantized Linear Computations by Ching-Fang Li, Mary Wootters (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-00183.txt.
Introduction
Ching-Fang Li and Mary Wootters sharpen the limits on a clever compression puzzle: answering many linear questions about a data vector by reading only a few entries of its encoded form. The encoding spreads the data across more numbers than it starts with, and the question is how few reads can still recover any weighted sum, rounded to a grid.
The authors prove stronger impossibility results than were known, both for all schemes and for the block-based family earlier work had proposed, showing that family cannot be beaten on its own terms. They then open a new direction: settling for approximate answers. Their constructions for a ten-percent error allowance beat what exact schemes can do, hinting approximation buys real savings.
Catalog record
| CREATOR | Ching-Fang Li, Mary Wootters |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 32 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2508-00183
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Improved Bounds on Access-Redundancy Tradeoffs in Quantized Linear Computations Ching-Fang Li, Mary Wootters Abstract Consider the problem of computing quantized linear functions with only a few queries. Formally, given 𝐱 ∈ ℝ k \mathbf{x}\in\mathbb{R}^{k} , our goal is to encode 𝐱 \mathbf{x} as 𝐜 ∈ ℝ n \mathbf{c}\in\mathbb{R}^{n} , for n > k n>k , so that for any 𝐰 ∈ 𝒜 k \mathbf{w}\in\mathcal{A}^{k} , 𝐰 T 𝐱 \mathbf{w}^{T}\mathbf{x} can be computed using at most ℓ \ell queries to 𝐜 \mathbf{c} . Here, 𝒜 \mathcal{A} is some finite set; in this paper we focus on the case where | 𝒜 | = 2 |\mathcal{A}|=2 . Prior work (Ramkumar, Raviv, and Tamo, Trans. IT, 2024) has given constructions and established impossibility results for this problem. We give improved impossibility results, both for the general problem, and for the specific class of construction (block construction) presented in that work. The latter establishes that the block constructions of prior work are optimal within that class. We also initiate the study of approximate recovery for this problem, where the goal is not to recover 𝐰 T 𝐱 \mathbf{w}^{T}\mathbf{x} exactly but rather to approximate it up to a parameter ε > 0 \varepsilon>0 . We give several constructions, and give constructions for ε = 0.1 \varepsilon=0.1 that outperform our impossibility result for exact schemes. I Introduction In this paper we consider the problem of computing quantized linear functions of data with a few queries. Formally, consider the set of linear functions \mathcal{F}_{\mathcal{A}}=\{f_{\mathbf{w}}\mid\mathbf{w}\in\mathcal{A}^{k}\} for some finite set \mathcal{A} , where f_{\mathbf{w}}:{\mathbb{R}}^{k}\to\mathbb{R} is given by f_{\mathbf{w}}(\mathbf{x})={\mathbf{w}}^{T}{\mathbf{x}}. The goal is to encode \mathbf{x}\in\mathbb{R}^{k} into some \mathbf{y}\in\mathbb{R}^{n} , for n\geq k , so that, for all f\in\mathcal{F} , it is possible to recover f(\mathbf{x}) given only \ell\leq n queries to the symbols of \mathbf{y} . The parameters of interest are the redundancy ratio \nu=n/k , which captures the amount of overhead in the encoding; and the access ratio \lambda=\ell/k , which captures the query complexity. We would like both to be as small as possible. If there is an infinite family of coding schemes that achieves the parameters (\nu,\lambda) , we say that this pair is feasible (see Definition 2 ). Understanding the set of feasible pairs, and coming up with code constructions that achieve them, is motivated by applications in distributed ML and coded computation. (See the discussion in [ 1 , 2 , 3 ] . Briefly, we imagine that \mathbf{x} is stored by storing the symbols of \mathbf{y} each at different nodes in a distributed system. Our goal is to compute f(\mathbf{x}) while accessing as few nodes as possible). This problem has been studied for various families \mathcal{F} over various domains. If \mathbf{x}\in\mathbb{F}^{k} for some finite field \mathbb{F} , and if \mathcal{A}=\mathbb{F} , then the problem is equivalent to the existence of linear covering codes (see [ 4 ] and the discussion in [ 1 ] ). Over \mathbb{R} , [ 5 ] showed how to use covering codes (in a different way) to obtain nontrivial constructions for \mathcal{A}=\{0,1\} . This was later improved by [ 1 ] for any \mathcal{A}\subseteq\mathbb{R}^{k} with |\mathcal{A}|=2 : That work showed that the problem is equivalent for any \mathcal{A} with |\mathcal{A}|=2 , and provided both improved constructions and impossibility results. In further work, [ 2 , 3 ] investigated the setting where |\mathcal{A}|>2 . Our Contributions. In this paper, we work in the setting of [ 5 , 1 ] , where |\mathcal{A}|=2 . As in prior work, we focus on schemes with linear encoding and decoding maps. Our main contributions are the following. • Improved Lower Bounds on \nu,\lambda . In [ 1 ] , an impossibility result is proved on the set of feasible points (\nu,\lambda). Using covering designs , we are able to improve this bound (Theorem 2 ; see also Corollary 1 ). A comparison of the our new bound with the bound from prior work is shown in Figure 1 . We further prove specialized lower bounds for the class of constructions in [ 1 ] . That work presents a class of block constructions , described more below, where \mathbf{x}\in\mathbb{R}^{k} is broken up into m blocks in \mathbb{R}^{k_{0}} , and each block is encoded separately. We prove a lower bound for any block construction (Theorem 3 ), and we show that the constructions presented in [ 1 ] in fact meet these bounds. We also present a new block construction (given in ( 4 ) and also shown in Figure 1 ) to demonstrate that other block constructions on our lower bound are achievable. • Initiating the study of approximate recovery. Prior work has focused on recovering f(\bm{x}) exactly for all f\in\mathcal{F} . In this work, we consider a relaxation (again for quantized linear functions with |\mathcal{A}|=2 ), where it is sufficient to estimate f(\mathbf{x}) up to error \varepsilon . We give three types of constructions for such approximation schemes, and show that even for \varepsilon=0.1 , it is possible to outperform our improved lower bound for exact reconstruction. Our constructions are shown in Figure 2 . Outline. In Section II , we set notation and formally define the problem, as well as formally present a few of the results in [ 1 ] that will be relevant for our work. In Section III , we present our improved general lower bound (Theorem 2 ), as well as our lower bound for block constructions (Theorem 3 ). In Section IV , we set up the approximate recovery problem, and present our constructions. II Preliminaries All vectors are column vectors. For a vector \mathbf{x}\in\mathbb{R}^{k} , the entries are written as (x_{1},x_{2},\dots,x_{k}) . We use \left\lVert\mathbf{x}\right\rVert_{0} to denote the number of nonzero entries of \mathbf{x} . We let [n]=\{1,2,\dots,n\} . For a finite set \mathcal{T} and an integer 0\leq\ell\leq|\mathcal{T}| , \binom{\mathcal{T}}{\ell} refers to the collection of all size- \ell subsets of \mathcal{T} . For a set \mathcal{S}\subseteq[n] and a matrix \mathbf{D} with n columns, \mathbf{D}|_{\mathcal{S}} denotes the set of columns of \mathbf{D} indexed by \mathcal{S} . Logarithms are of base 2 if not otherwise specified. II-A Problem Statement As stated in the introduction, our goal is to design an encoding map that maps \mathbf{x}\in\mathbb{R}^{k} to \mathbf{y}\in\mathbb{R}^{n} . We will restrict to linear codes, meaning that the encoding map is given by \mathbf{y}=\mathbf{D}^{T}\mathbf{x} for some matrix \mathbf{D}\in\mathbb{R}^{k\times n} . For any function f:\mathbb{R}^{k}\to\mathbb{R} in some function class \mathcal{F} , we would like to be able to recover f(\mathbf{x}) given at most \ell queries to the symbols of \mathbf{y} . We focus on quantized linear computations by considering the function class \mathcal{F}_{\mathcal{A}}=\left\{f_{\mathbf{w}}\,\middle|\,\mathbf{w}\in\mathcal{A}^{k}\right\} where f_{\mathbf{w}}(\mathbf{x})=\mathbf{w}^{T}\mathbf{x} , for some finite coefficient set \mathcal{A}\subset\mathbb{R} . We also restrict our attention to linear decoding maps. That is, for each f\in\mathcal{F}_{\mathcal{A}}, we want that f(\mathbf{x}) can be represented as some linear combination of at most \ell entries of \mathbf{y}. Since everything we wish to compute is linear, we may rephrase the problem in terms of linear algebra. Formally, we define a \mathcal{A} -protocol as follows. Definition 1 ( \mathcal{A} -protocol) . Fix a finite set \mathcal{A}\subseteq\mathbb{R} , and let s=|\mathcal{A}|^{k} . Let \mathbf{W}\in\mathbb{R}^{k\times s} be a matrix that has each \mathbf{w}\in\mathcal{A}^{k} as a column. A \mathcal{A} -protocol with parameters (k,n,\ell) consists