CS Paper Radar

Compression of Sources with Memory and Private Random Access

Venkat Chandar, Aslan Tchamkerten, Shashank Vatedka

cs.IT ·submitted 2026-11-08 17:01 UTC · v1

Abstract

Private local decoding imposes a stringent constraint on compression: the codeword bits used to recover a source symbol must reveal nothing about the remaining symbols beyond what the recovered symbol itself reveals. For memoryless sources, this constraint is known to be compatible with entropy-rate compression. We show that the same holds for any stationary ergodic source over a finite alphabet. Specifically, every rate above the entropy rate is achievable with exact privacy and error-free local decoding on a set of source sequences whose probability tends to one. In contrast, we exhibit non-ergodic sources for which private local decoding incurs a strictly positive rate penalty.

Comment
22 pages, 2 figures

Closest papers

Nearest neighbours by meaning across the whole index.

Exact Minimax One-Bit Unbiased Compression: Heavy-Tail Necessity and Finite-Randomness Approximation

cs.LG ·2026-08-20 ·Tao Jiang, Minbo Gao, Shaowei Cai
theoryhot direction similarity 0.61
Abstract

A pointwise-unbiased one-bit compressor reconstructs every real input in expectation while transmitting one bit. For a scalar source $P$ with CDF $F$, mean $m$, and $\mathcal J(P)=\int_{\mathbb R}\sqrt{F(r)(1-F(r))}\,dr$, we prove that the infimum of the source-averaged reconstruction second moment over all public-coin one-bit codes unbiased on $\mathbb R$ is $m^2+\mathcal J(P)^2$. For regular full-support sources, a distribution-centered random-threshold code attains this value; a converse over arbitrary randomized binary encoders and an equality analysis characterize every attaining code up to null sets, bit relabeling, and public-seed refinement. For the Gaussian location family $\mathcal N(μ,σ^2)$ with $|μ|\le cσ$, the equal prior on the endpoint means is least favorable and the minimax value is $σ^2Λ_c^2$. Exact Gaussian minimax optimality forces a critical heavy tail: at the endpoint means, absolute moments are finite exactly for $p<3$, and $\Pr(W>t)=Θ(t^{-3}/\sqrt{\log t})$. A Cauchy-mixture robustification inflates the second moment by at most $1/(1-η)$ while making every positive-order absolute moment finite. Finite-support public randomness with finite decoder means cannot achieve exact unbiasedness on $\mathbb R$, but a bounded-output approximation using exactly $R$ shared random bits has explicit bias and second-moment bounds converging to the minimax constant. Finally, coordinate allocation communicates exactly $B$ bits per Gaussian-gradient query. On Kim's continuous quadratic hard family, the expected optimization guarantee matches the lower bound in its dependence on $(σ,d,B,\varepsilon)$, and a finite-variance high-probability bound incurs only a logarithmic confidence factor.

0.24

Quadratic Extractors

cs.CC cs.CRmath.CO ·2026-11-05 ·Gautam Chandrasekaran, Jesse Goodman, David Zuckerman
similarity 0.60
Abstract

A quadratic source is a random variable $X\sim\mathbb{F}_2^n$ generated by applying $n$ quadratics to a hidden uniform string. Previously, the best-known explicit extractor for this model required min-entropy roughly $k=n-\sqrt{\log n}$. In this paper, we give an explicit construction for min-entropy $k=\mathrm{polylog}(n)$. Even for the special case of $2$-local sources, where each bit of $X$ depends on two hidden uniform bits, achieving an entropy requirement below $k=\sqrt{n}$ was an important open problem. This is because such sources provably cannot be reduced (in a black-box manner) to our most powerful general-purpose seedless extractor, known as a sumset extractor. Our new extractor bypasses this barrier, providing the first explicit construction to go beyond sumset extraction.

0.23

Second-Order Expansion of Privacy Amplification Under f-Divergence Criteria

cs.IT ·2026-09-10 ·Mario Berta, Hao-Chung Cheng, Marco Tomamichel
similarity 0.59
Abstract

We derive the second-order asymptotics of randomness extraction from memoryless sources with side information under security criteria based on a broad class of Csiszàr f-divergences, treating both a fixed reference side-information marginal and optimization over that marginal. The conditional varentropy decomposes into fluctuations of the conditional entropy across different values of the side information and the average variance of the conditional surprisal for each value. Without marginal optimization, these contributions yield a Gaussian-mixture second-order profile. With marginal optimization, they combine into the total conditional varentropy, yielding a single Gaussian profile. As corollaries, we obtain second-order expansions for Rényi-entropy criteria of all orders $α\in (0,1)$ and recover the known expansion for total variation distance.

0.30

On the Complexity of Symmetric Boolean Functions in Multiparty Private Simultaneous Messages

cs.CR cs.CC ·2026-10-15 ·Marshall Ball, Peter Crawford-Kahrl, Vladimir Podolskii, Morgan Prior
theory similarity 0.59
Abstract

Multiparty Private Simultaneous Messages (PSM), also known as Decomposable Randomized Encoding (DRE) or information-theoretic garbling, is a model for non-interactive secure computation. Each party encodes its input using shared randomness and sends a message to an evaluator who does not know that randomness. The evaluator must recover the function output without learning anything else about the inputs. Perfect privacy requires identical transcript distributions on inputs with the same output. We also study the weaker notion of support privacy, which requires only that these distributions have the same support. We study the communication complexity of symmetric Boolean functions when each of the $n$ parties holds one input bit. Lower bounds. We prove a superlinear lower bound for support-private PSM protocols computing $OR_n$. Our technique gives $Ω(n\log n)$ lower bounds for $MAJ_n$ and $EMAJ_n$ (with even $n$), and an $Ω(n\log q)$ lower bound for $MOD_q$ when $q\leq(1-c)n$ for a fixed constant $c>0$. Upper bounds. We construct perfectly private PSM protocols of total communication $\widetilde{O}(n^{3/2})$ for every symmetric Boolean function, improving on the known quadratic bound. For $MAJ_n$, known branching-program constructions yield an upper bound of $O(n\log^3 n\log\log n)$. For $EMAJ_n$ and $MOD_q$ with prime $q$, the lower bounds are tight up to constant factors in the stated regimes. Under support privacy, we obtain $\widetilde{O}(n)$ communication for every symmetric Boolean function. Earlier lower-bound techniques of Ball et al. (ITCS 2020) yield only trivial linear bounds for symmetric Boolean functions. Concurrent and independent work by Holmgren and Wu proves a $ω(n)$ lower bound for $OR_n$ using the same combinatorial core. Both works used AI assistance.

0.14

A $π/ 4$ lower bound for random access in symmetric linear ensembles under optimal decoding

cs.IT ·2026-10-28 ·Daniella Bar-Lev, Ohad Elishco, Ryan Gabrys
theory similarity 0.59
Abstract

We study the expected number of random linear observations required to recover a prescribed information symbol. For ensembles with uniformly random supports, independently sampled nonzero coefficients, and uniformly bounded column weights, we prove that the asymptotic normalized expected recovery time is at least $π/4$ under optimal decoding. The result holds over finite or infinite fields and extends the lower bound previously established for binary fully symmetric codes under peeling decoding. For singleton - pair observations, we determine the exact limiting expectation and show that optimal and peeling decoding have the same limit, independently of the field and coefficient distribution. The minimum within this family is approximately $0.793933445$, which explicit constructions attain asymptotically over every fixed finite field.

0.47

Polynomial-Time Constructions of Asymptotically Good Random Access Codes from Linear Codes

cs.IT ·2026-10-28 ·Ruho Kondo, Yota Maeda
similarity 0.58
Abstract · 13 pages, 5 figures,

Random access codes (RACs) encode a $q$-ary input string into fewer $q$-ary symbols while allowing any requested input symbol to be recovered with probability above the random-guessing value $1/q$. However, it remains unclear what asymptotic guarantees on compression and recovery probability should be required of RACs. We address this question by introducing the notion of asymptotically good RACs and give two polynomial-time constructions. First, an $[n,k,d]_q$ linear code with $d\ge2$, together with an encoder based on its orthogonal-array property, yields an $(n,n-k)_q$-RAC with worst-case decoding success probability \[ p_{\rm wc}=\frac{1}{q}+\left(1-\frac{1}{q}\right)\frac{d-2}{n}. \] These OA-RACs are asymptotically good whenever the underlying linear codes are, and Garcia--Stichtenoth algebraic-geometry codes give a concrete polynomial-time realization. Second, a direct-sum strategy using OA-RACs derived from $q$-ary Hamming codes and the trivial $(1,1)_q$-RAC yields asymptotically good RAC families at every prescribed RAC rate $R_{\rm RAC}=(n-k)/n\in(0,1)$. Numerical results demonstrate favorable finite-length performance of both constructions.

0.23

Lossless Source Coding with Marginal Distribution Constraint

cs.IT ·2026-11-04 ·Cheuk Ting Li, Jun Chen, Shahab Asoodeh
similarity 0.58
Abstract · 15 pages

We consider lossless source coding with a marginal distribution constraint on the encoding symbols (SC-MDC). Unlike distribution matching, signal shaping and homophonic coding which require the symbols to be (approximately) i.i.d. following a target distribution, SC-MDC requires each symbol to have a marginal distribution that exactly matches the target distribution, which can be regarded as a perfect perceptual quality constraint on the symbols, and may have applications to wear leveling, source coding with cost and steganography. We give nonasymptotic lower and upper bounds on the optimal encoding length, and exactly characterize the coding rate (or the first-order term of the length) when the source distribution or the target distribution is uniform, or when the source is an i.i.d. sequence.

0.26

Universal Decoding for Unequal Error Protection

cs.IT ·2026-10-11 ·Seyed AmirPouya Moeini, Albert Guillén i Fàbregas
similarity 0.58
Abstract

We study universal unequal error protection of a single special message over discrete memoryless channels. We construct a sequence of codes with a decoding rule that does not depend on the channel transition law. We derive an achievable error exponent for the special message while ensuring reliable decoding of the ordinary messages. The resulting exponent strictly improves on the natural equal-error-protection random-coding baseline and remains positive as the rate approaches capacity. For symmetric channels, it converges to the optimal red-alert exponent at capacity.

0.17