Search

A linear error correcting code is a subspace of a finite-dimensional space over a finite field with a fixed coordinate system. Such a code is said to be locally recoverable with locality r if, for every coordinate, its value at a codeword can be deduced from the value of (certain) r other coordinates of the codeword. These codes have found many recent applications, e.g., to distributed cloud storage. We will discuss the problem of constructing good locally recoverable codes and present some constructions using algebraic surfaces that improve previous constructions and sometimes provide codes that are optimal in a precise sense. The main conceptual contribution of this paper is to consider surfaces fibered over a curve in such a way that each recovery set is constructed from points in a single fiber. This allows us to use the geometry of the fiber to guarantee the local recoverability and use the global geometry of the surface to get a hold on the standard parameters of our codes. We look in detail at situations where the fibers are rational or elliptic curves and provide many examples applying our methods. [ABSTRACT FROM AUTHOR]

In this paper, we provide two complementary results for cyclic codes of composite length. First, we give a general construction of cyclic codes of length nr from cyclic codes of length n and a lower bound on the minimum distance. Numerical data show that many cyclic codes of composite length with the best parameters can be obtained in this way. Second, in the other direction, we show that for cyclic codes of length n with a primitive n-th root of unity as a non-zero, the minimum distance is roughly bounded by the square-free part of n. This means that we shall not expect good cyclic codes of length n in general if, for example, the length n is divisible by a high power of a prime. [ABSTRACT FROM AUTHOR]

We introduce two notions of discrepancy between binary vectors, which are not metric functions in general but nonetheless capture the mathematical structure of the binary asymmetric channel. These lead to two new fundamental parameters of binary error-correcting codes, both of which measure the probability that the maximum likelihood decoder fails. We then derive various bounds for the cardinality and weight distribution of a binary code in terms of these new parameters, giving examples of codes meeting the bounds with equality. [ABSTRACT FROM AUTHOR]

We consider the average age of information in G/G/1/1 systems under two service discipline models. In the first model, if a new update arrives when the service is busy, it is blocked; in the second model, a new update preempts the current update in service. For the blocking model, we first derive an exact age expression for G/G/1/1 systems. Then, using the age expression for G/G/1/1 systems, we calculate average age expressions for special cases, i.e., M/G/1/1 and G/M/1/1 systems. We observe that deterministic interarrivals minimize the average age of G/M/1/1 systems for a given mean interarrival time. Next, for the preemption in service model, we first derive an exact average age expression for G/G/1/1 systems. Then, similar to blocking discipline, using the age expression for G/G/1/1 systems, we calculate average age expressions for special cases, i.e., M/G/1/1 and G/M/1/1 systems. Average age for G/M/1/1 can be written as a summation of two terms, the first of which depends only on the first and second moments of interarrival times and the second of which depends only on the service rate. In other words, interarrival and service times are decoupled. We prove that deterministic interarrivals are optimum for G/M/1/1 systems for a given mean interarrival time. On the other hand, we observe for non-exponential service times that the optimal distribution of interarrival times depends on the relative values of the mean interarrival time and the mean service time. Finally, we propose a simple to calculate upper bound to the average age for the preemption in service discipline. [ABSTRACT FROM AUTHOR]

An improved Singleton-type upper bound is presented for the list decoding radius of linear codes, in terms of the code parameters $[n,k,d]$ and the list size $L$. $L$ -MDS codes are then defined as codes that attain this bound (under a slightly stronger notion of list decodability), with 1-MDS codes corresponding to ordinary linear MDS codes. Several properties of such codes are presented; in particular, it is shown that the 2-MDS property is preserved under duality. Finally, explicit constructions for 2-MDS codes are presented through generalized Reed–Solomon (GRS) codes. [ABSTRACT FROM AUTHOR]

We analyze the convergence rates of $k$ nearest neighbor density estimation method, under $\ell _{\alpha} $ norm with $\alpha \in [1,\infty]$. Our analysis includes two different cases depending on whether the support set is bounded or not. In the first case, the probability density function has a bounded support. We show that if the support set is known, then the kNN density estimator is minimax optimal under $\ell _{\alpha} $ with both $\alpha \in \big[1,\infty\big)$ and $\alpha =\infty $. If the support is unknown, the kNN density estimator is still minimax optimal under $\ell _{1}$ , but is suboptimal under $\ell _{\alpha} $ for $\alpha >1$ , and not consistent under $\ell _\infty $. In the second case, the support is unbounded and the probability density function is smooth everywhere. Moreover, the Hessian is assumed to decay with the density values. For this case, our result shows that the $\ell _\infty $ error of kNN density estimation is nearly minimax optimal. The $\ell _{\alpha} $ error for the original kNN density estimator is not consistent. To address this issue, we design a new adaptive kNN estimator, which can select different $k$ for different samples. Using this adaptive estimator, the $\ell _{\alpha} $ bound is minimax optimal. For comparison, we show that the popular kernel density estimator is not minimax optimal for this case. [ABSTRACT FROM AUTHOR]

Minimum energy required to achieve a distortion-noise profile, i.e., a function indicating the maximum allowed distortion value for each channel noise level, is studied for transmission of Gaussian sources over Gaussian channels. A general coding scheme is proposed to upper bound the minimum energy needed for any distortion-noise profile. Conversely, utilizing a family of lower bounds originally derived for broadcast channels with power constraints, the minimum required energy is lower bounded for any profile. As examples, linear, exponential, square-law, and staircase profiles are studied. It is shown that for the linear profile, as well as for any concave profile, uncoded transmission is optimal. As a negative result, it is shown that exponential profiles are not achievable with finite energy. For square-law and staircase profiles, upper bounds and lower bounds are derived and the gaps between them are studied. [ABSTRACT FROM AUTHOR]

We analyze the best achievable performance of Bayesian learning under generative models by defining and upper-bounding the minimum excess risk (MER): the gap between the minimum expected loss attainable by learning from data and the minimum expected loss that could be achieved if the model realization were known. The definition of MER provides a principled way to define different notions of uncertainties in Bayesian learning, including the aleatoric uncertainty and the minimum epistemic uncertainty. Two methods for deriving upper bounds for the MER are presented. The first method, generally suitable for Bayesian learning with a parametric generative model, upper-bounds the MER by the conditional mutual information between the model parameters and the quantity being predicted given the observed data. It allows us to quantify the rate at which the MER decays to zero as more data becomes available. Under realizable models, this method also relates the MER to the richness of the generative function class, notably the VC dimension in binary classification. The second method, particularly suitable for Bayesian learning with a parametric predictive model, relates the MER to the minimum estimation error of the model parameters from data via various continuity arguments. We also extend the definition and analysis of MER to the setting with multiple model families and the setting with nonparametric models. Along the discussions we draw some comparisons between the MER in Bayesian learning and the excess risk in frequentist learning. [ABSTRACT FROM AUTHOR]

We study codes with parameters of $q$ -ary shortened Hamming codes, i.e., $(n=(q^{m}-q)/(q-1), q^{n-m}, 3)_{q}$. Firstly, we prove the fact mentioned in 1998 by Brouwer et al. that such codes are optimal, generalizing it to a bound for multifold packings of radius-1 balls, with a corollary for multiple coverings. In particular, we show that the punctured Hamming code is an optimal $q$ -fold packing with minimum distance 2. Secondly, for every admissible length starting from $n=20$ , we show the existence of 4-ary codes with parameters of shortened 1-perfect codes that cannot be obtained by shortening a 1-perfect code. [ABSTRACT FROM AUTHOR]

We prove a tight and close-to-optimal lower bound on the effectiveness of local quantum measurements (without classical communication) at discriminating any two bipartite quantum states. Our result implies, for example, that any two orthogonal quantum states of a $n_{A}\times n_{B}$ bipartite quantum system can be discriminated via local measurements with an error probability no larger than $\frac {1}2 \left ({1 - \frac {1}{c \min \{n_{A}, n_{B}\}} }\right)$ , where $1\leq c\leq 2\sqrt {2}$ is a universal constant, and our bound scales provably optimally with the local dimensions $n_{A},n_{B}$. Mathematically, this is achieved by showing that the distinguishability norm $\|\cdot \|_{ \mathrm {LO}}$ associated with local measurements satisfies that $\|\cdot \|_{1}\leq 2\sqrt {2} \min \{n_{A},n_{B}\} \|\cdot \|_{ \mathrm {LO}}$ , where $\|\cdot \|_{1}$ is the trace norm. [ABSTRACT FROM AUTHOR]

Large pools of synthetic DNA molecules have been recently used to reliably store significant volumes of digital data. While DNA as a storage medium has enormous potential because of its high storage density, its practical use is currently severely limited because of the high cost and low throughput of available DNA synthesis technologies. We study the role of batch optimization in reducing the cost of large scale DNA synthesis, which translates to the following algorithmic task. Given a large pool $\mathcal {S}$ of random quaternary strings of fixed length, partition $\mathcal {S}$ into batches in a way that minimizes the sum of the lengths of the shortest common supersequences across batches. We introduce two ideas for batch optimization that both improve (in different ways) upon a naive baseline: (1) using both $(ACGT)^{\ast}$ and its reverse $(TGCA)^{\ast}$ as reference strands, and batching appropriately, and (2) batching via the quantiles of an appropriate ordering of the strands. We also prove asymptotically matching lower bounds on the cost of DNA synthesis, showing that one cannot improve upon these two ideas. Our results uncover a surprising separation between two cases that naturally arise in the context of DNA data storage: the asymptotic cost savings of batch optimization are significantly greater in the case where strings in $\mathcal {S}$ do not contain repeats of the same character (homopolymers), as compared to the case where strings in $\mathcal {S}$ are unconstrained. [ABSTRACT FROM AUTHOR]

The (classical) crosscorrelation is an important measure of pseudorandomness of two binary sequences for applications in communications. The arithmetic crosscorrelation is another figure of merit introduced by Goresky and Klapper generalizing Mandelbaum’s arithmetic autocorrelation. First we observe that the arithmetic crosscorrelation is constant for two binary sequences of coprime periods, which complements the analogous result for the classical crosscorrelation. Then we prove upper bounds for the constant arithmetic crosscorrelation of two Legendre sequences of different periods and of two binary $m$ -sequences of coprime periods, respectively. [ABSTRACT FROM AUTHOR]

We prove that for $n$ sufficiently large, all perfect 3-hash linear codes in $\mathbb {F}_{3}^{n}$ must have dimension at most $\left ({\frac {1}{4}-\epsilon }\right)n$ for some absolute constant $\epsilon > 0$. [ABSTRACT FROM AUTHOR]

Optimal rates for achieving an information processing task are often characterized in terms of regularized information measures. In many cases of quantum tasks, we do not know how to compute such quantities. Here, we exploit the symmetries in the recently introduced $\mathrm {D}^{\#}$ in order to obtain a hierarchy of semidefinite programming bounds on various regularized quantities. As applications, we give a general procedure to give efficient bounds on the regularized Umegaki channel divergence as well as the classical capacity and two-way assisted quantum capacity of quantum channels. In particular, we obtain slight improvements for the capacity of the amplitude damping channel. We also prove that for fixed input and output dimensions, the regularized sandwiched Rényi divergence between any two quantum channels can be approximated up to an $\epsilon $ accuracy in time that is polynomial in $1/\epsilon $. [ABSTRACT FROM AUTHOR]

We extend upper bounds on the quantum independence number and the quantum Shannon capacity of graphs to their counterparts in the commuting operator model. We introduce a von Neumann algebraic generalization of the fractional Haemers bound (over $\mathbb {C}$) and prove that the generalization upper bounds the commuting quantum independence number. We call our bound the tracial Haemers bound, and we prove that it is multiplicative with respect to the strong product. In particular, this makes it an upper bound on the Shannon capacity. The tracial Haemers bound is incomparable with the Lovász theta function, another well-known upper bound on the Shannon capacity. We show that separating the tracial and fractional Haemers bounds would refute Connes’ embedding conjecture. Along the way, we prove that the tracial rank and tracial Haemers bound are elements of the (commuting quantum) asymptotic spectrum of graphs (Zuiddam, Combinatorica, 2019). We also show that the inertia bound (an upper bound on the quantum independence number) upper bounds the commuting quantum independence number. [ABSTRACT FROM AUTHOR]

Trace reconstruction considers the task of recovering an unknown string $\mathbf {x}\in \{0,1\}^{n}$ given a number of independent “traces”, i.e., subsequences of $\mathbf {x}$ obtained by randomly and independently deleting every symbol of $\mathbf {x}$ with some probability $p$. The information-theoretic limit of the number of traces needed to recover a string of length $n$ is still unknown. This limit is essentially the same as the number of traces needed to determine, given strings $\mathbf {x}$ and $\mathbf {y}$ and traces of one of them, which string is the source. The most-studied class of algorithms for the worst-case version of the problem are “mean-based” algorithms. These are a restricted class of distinguishers that only use the mean value of each coordinate on the given samples. In this work we study limitations of mean-based algorithms on strings at small Hamming or edit distance. We show that, on the one hand, distinguishing strings that are nearby in Hamming distance is “easy” for such distinguishers. On the other hand, we show that distinguishing strings that are nearby in edit distance is “hard” for mean-based algorithms. Along the way, we also describe a connection to the famous Prouhet-Tarry-Escott (PTE) problem, which shows a barrier to finding explicit hard-to-distinguish strings: namely such strings would imply explicit short solutions to the PTE problem, a well-known difficult problem in number theory. Furthermore, we show that the converse is also true, thus, finding explicit solutions to the PTE problem is equivalent to the problem of finding explicit strings that are hard-to-distinguish by mean-based algorithms. Our techniques rely on complex analysis arguments that involve careful trigonometric estimates, and algebraic techniques that include applications of Descartes’ rule of signs for polynomials over the reals. [ABSTRACT FROM AUTHOR]

The DNA storage channel is considered, in which the $M$ Deoxyribonucleic acid (DNA) molecules comprising each codeword are stored without order, sampled $N$ times with replacement, and then sequenced over a discrete memoryless channel. For a constant coverage depth $M/N$ and molecule length scaling $\Theta (\log M)$ , lower (achievability) and upper (converse) bounds on the capacity of the channel, as well as a lower (achievability) bound on the reliability function of the channel are provided. Both the lower and upper bounds on the capacity generalize a bound which was previously known to hold only for the binary symmetric sequencing channel, and only under certain restrictions on the molecule length scaling and the crossover probability parameters. When specified to binary symmetric sequencing channel, these restrictions are completely removed for the lower bound and are significantly relaxed for the upper bound in the high-noise regime. The lower bound on the reliability function is achieved under a universal decoder, and reveals that the dominant error event is that of outage – the event in which the capacity of the channel induced by the DNA molecule sampling operation does not support the target rate. [ABSTRACT FROM AUTHOR]

A function $F: \mathbb {F}_{2}^{n}\rightarrow \mathbb {F} _{2}^{n}$ , $n=2m$ , can have at most $2^{n}-2^{m}$ bent component functions. Trivial examples are vectorial bent functions from $\mathbb {F}_{2}^{n}$ to $\mathbb {F}_{2}^{m}$ , seen as functions on $\mathbb {F}_{2}^{n}$. The first nontrivial example is given in univariate form as $x^{2^{r}} {\rm Tr^{n}_{m}}(x), 1\le r < m$ (Pott et al. 2018), a few more examples of similar shape are given by Mesnager et al. 2019, and finally it has been shown that the quadratic function $F(x) = x^{2^{r}} {\rm Tr^{n}_{m}}(\Lambda (x))$ , has $2^{n}-2^{m}$ bent components if and only if $\Lambda $ is a linearized permutation polynomial of $\mathbb {F}_{2^{m}}[x]$ (Anbar et al. 2021). In the first part of this article, an upper bound for the nonlinearity of plateaued functions with $2^{n}-2^{m}$ bent components is shown, which is attained by the example $x^{2^{r}} {\rm Tr^{n}_{m}}(x)$. We then analyse in detail nonlinearity and differential spectrum of the class of functions $F(x) = x^{2^{r}} {\rm Tr^{n}_{m}}(\Lambda (x))$ , which, as will be seen, requires the study of the functions $x^{2^{r}}\Lambda (x)$. In the last part we demonstrate that this class belongs to a larger class of functions with $2^{n}-2^{m}$ Maiorana-McFarland bent components, which also contains nonquadratic and non-plateaued functions. [ABSTRACT FROM AUTHOR]

Many known networks have structure of affiliation networks, where each of $n$ network nodes (actors) selects an attribute set from a given collection of $m$ attributes, and two nodes (actors) establish adjacency relation whenever they share a common attribute. We study the behavior of a random walk on such networks. For this purpose, we use a common model of such networks, a random intersection graph. We establish the cover time of the simple random walk on the binomial random intersection graph ${\mathcal{ G}}(n,m,p)$ at the connectivity threshold and above it. We consider the range of $(n,m,p)$ , where the typical attribute is shared by a (stochastically) bounded number of actors. [ABSTRACT FROM AUTHOR]

We propose a new method to compute the feedback capacity of unifilar finite state channels (FSCs) with memory using reinforcement learning (RL). The feedback capacity was previously estimated using its formulation as a Markov decision process (MDP) with dynamic programming (DP) algorithms. However, their computational complexity grows exponentially with the channel alphabet size. Therefore, we use RL, and specifically, its ability to parameterize value functions and policies with neural networks, to evaluate numerically the feedback capacity of channels with a large alphabet size. The outcome of the RL algorithm is a numerical lower bound on the feedback capacity, which is used to reveal the structure of the optimal solution. The structure is modeled by a graph-based auxiliary random variable that is utilized to derive an analytic upper bound on the feedback capacity with the duality bound. The capacity computation is concluded by verifying the tightness of the upper bound by testing whether it is Bahl-Cocke-Jelinek-Raviv (BCJR) invariant. We demonstrate this method on the Ising channel with an arbitrary alphabet size. For an alphabet size smaller than or equal to 8, we derive the analytic solution of the capacity. Next, the structure of the numerical solution is used to deduce a simple coding scheme that achieves the feedback capacity and serves as a lower bound for larger alphabets. For an alphabet size greater than 8, we present an upper bound on the feedback capacity. For an asymptotically large alphabet size, we present an asymptotic optimal coding scheme. [ABSTRACT FROM AUTHOR]

We construct a family of $(n,k)$ convolutional codes with degree $\delta \in \{k,n-k\}$ that have a maximum distance profile. The field size required for our construction is $\Theta (n^{2\delta })$ , which improves upon the known constructions of convolutional codes with a maximum distance profile. Our construction is based on the theory of skew polynomials. [ABSTRACT FROM AUTHOR]

We develop a new upper bound on the capacity of the relay channel that is tighter than previously known upper bounds. This upper bound is proved using traditional weak converse techniques involving mutual information inequalities and Gallager-type explicit identification of auxiliary random variables. We show that the new upper bound is strictly tighter than all previous bounds for the Gaussian relay channel with non-zero channel gains. When specialized to the relay channel with orthogonal receiver components, the bound resolves a conjecture by Kim on a class of deterministic relay channels. When further specialized to the class of product-form relay channels with orthogonal receiver components, the bound resolves a generalized version of Cover’s relay channel problem, recovers the recent upper bound for the Gaussian case by Wu et al., and improves upon the recent bounds for the binary symmetric case by Wu et al. and Barnes et al., which were obtained using non-traditional geometric proof techniques. For the special class of a relay channel with orthogonal receiver components, we develop another upper bound on the capacity which utilizes an auxiliary receiver and show that it is strictly tighter than the bound by Tandon and Ulukus. Finally, we show through the Gaussian relay channel with i.i.d. relay output sequence that the bound with the auxiliary receiver can be strictly tighter than our main bound. [ABSTRACT FROM AUTHOR]

While quantum weight enumerators establish some of the best upper bounds on the minimum distance of quantum error-correcting codes, these bounds are not optimized to quantify the performance of quantum codes under the effect of arbitrary quantum channels that describe bespoke noise models. Herein, for any Kraus decomposition of any given quantum channel, we introduce corresponding quantum weight enumerators that naturally generalize the Shor-Laflamme quantum weight enumerators. We establish an indirect linear relationship between these generalized quantum weight enumerators by introducing an auxiliary exact weight enumerator that completely quantifies the quantum code’s projector, and is independent of the underlying noise process. By additionally working within the framework of approximate quantum error correction, we establish a general framework for constructing a linear program that is infeasible whenever approximate quantum error correcting codes with corresponding parameters do not exist. Our linear programming framework allows us to establish the non-existence of certain quantum codes that approximately correct amplitude damping errors, and obtain non-trivial upper bounds on the maximum dimension of a broad family of permutation-invariant quantum codes. [ABSTRACT FROM AUTHOR]

We study the Singleton-type bound that provides an upper limit on the minimum distance of locally repairable codes. We present an improved bound by carefully analyzing the combinatorial structure of the repair sets. Thus, we show the previous bound is unachievable for certain parameters. We then also provide explicit constructions of optimal codes which show that for certain parameters the new bound is sharp. Additionally, as a byproduct, some previously known codes are shown to attain the new bound and are thus proved to be optimal. [ABSTRACT FROM AUTHOR]

Mean-based reconstruction is a fundamental, natural approach to worst-case trace reconstruction over channels with synchronization errors. It is known that $\exp (\Theta (n^{1/3}))$ traces are necessary and sufficient for mean-based worst-case trace reconstruction over the deletion channel, and this result was also extended to certain channels combining deletions and geometric insertions of uniformly random bits. In this work, we use a simple extension of the original complex-analytic approach to show that these results are examples of a much more general phenomenon. We introduce oblivious synchronization channels, which map each input bit to an arbitrarily distributed sequence of replications and insertions of random bits. This general class captures all previously considered synchronization channels. We show that for any oblivious synchronization channel whose output length follows a sub-exponential distribution either mean-based trace reconstruction is impossible or $\exp (O(n^{1/3}))$ traces suffice for this task. [ABSTRACT FROM AUTHOR]

We study generalized covering radii, a fundamental property of linear codes that characterizes the trade-off between storage, latency, and access in linear data-query protocols such as PIR. We prove lower and upper bounds on the generalized covering radii of Reed-Muller codes, as well as finding their exact value in certain extreme cases. With the application to linear data-query protocols in mind, we also construct a covering algorithm that gets as input a set of points in space, and find a corresponding set of codewords from the Reed-Muller code that are jointly not farther away from the input than the upper bound on the generalized covering radius of the code. We prove that the algorithm runs in time that is polynomial in the code parameters. [ABSTRACT FROM AUTHOR]

Motivated by applications to DNA storage, we study reconstruction and list-reconstruction schemes for integer vectors that suffer from limited-magnitude errors. We characterize the asymptotic size of the intersection of error balls in relation to the code’s minimum distance. We also devise efficient reconstruction algorithms for various limited-magnitude error parameter ranges. We then extend these algorithms to the list-reconstruction scheme, and show the trade-off between the asymptotic list size and the number of required channel outputs. These results apply to all codes, without any assumptions on the code structure. Finally, we also study linear reconstruction codes with small intersection, as well as show a connection to list-reconstruction codes for the tandem-duplication channel. [ABSTRACT FROM AUTHOR]

A new converse bound is presented for the two-user multiple-access channel under the average probability of error constraint. This bound shows that for most channels of interest, the second-order coding rate—that is, the difference between the best achievable rates and the asymptotic capacity region as a function of blocklength $n$ with fixed probability of error—is $O(1/\sqrt {n})$ bits per channel use. The principal tool behind this converse proof is a new measure of dependence between two random variables called wringing dependence, as it is inspired by Ahlswede’s wringing technique. The $O(1/\sqrt {n})$ gap is shown to hold for any channel satisfying certain regularity conditions, which includes all discrete-memoryless channels and the Gaussian multiple-access channel. Exact upper bounds as a function of the probability of error are proved for the coefficient in the $O(1/\sqrt {n})$ term, although for most channels they do not match existing achievable bounds. [ABSTRACT FROM AUTHOR]

The generalized Poor-Verdú error lower bound established by Chang et al. (2020) for multihypothesis testing is studied in the classical channel coding context. It is proved that for any sequence of block codes sent over the memoryless binary symmetric channel (BSC), the minimum probability of error (under maximum likelihood decoding) has a relative deviation from the generalized bound that grows at most linearly in blocklength. This result directly implies that for arbitrary codes used over the BSC, decoder ties can only affect the subexponential behavior of the minimum probability of error. [ABSTRACT FROM AUTHOR]

List-decodability of Reed–Solomon codes has received a lot of attention, but the best-possible dependence between the parameters is still not well-understood. In this work, we focus on the case where the list-decoding radius is of the form $r=1-\varepsilon $ for $\varepsilon $ tending to zero. Our main result states that there exist Reed–Solomon codes with rate $\Omega (\varepsilon)$ which are $(1-\varepsilon, O(1/\varepsilon))$ -list-decodable, meaning that any Hamming ball of radius $1-\varepsilon $ contains at most $O(1/\varepsilon)$ codewords. This trade-off between rate and list-decoding radius is best-possible for any code with list size less than exponential in the block length. By achieving this trade-off between rate and list-decoding radius we improve a recent result of Guo, Li, Shangguan, Tamo, and Wootters, and resolve the main motivating question of their work. Moreover, while their result requires the field to be exponentially large in the block length, we only need the field size to be polynomially large (and in fact, almost-linear suffices). We deduce our main result from a more general theorem, in which we prove good list-decodability properties of random puncturings of any given code with very large distance. [ABSTRACT FROM AUTHOR]

We introduce a new analysis technique to derive a single-letter upper bound on the mismatch capacity of a stationary, single-user, memoryless channel with a decoding metric $q$. Our bound is obtained by considering a multicast transmission over a two-user broadcast channel with decoding metrics $q$ and $\rho $ at the receivers, referred to as $(q,\rho)$ -surely degraded. This channel has the property that the intersection event of correct $q$ -decoding of receiver 1 and erroneous $\rho $ -decoding of receiver 2 has zero probability for any fixed-composition codebook of a certain composition $P$. Our bound holds in the strong converse sense of an exponential decay of the probability of correct decoding at rates above the bound. Further, we refine the proof and present a bound that is tighter than that of any choice of $\rho $. Several examples that demonstrate the strict improvement of our bound compared to previous results are analyzed. Finally, we detect equivalence classes of isomorphic channel-metric pairs $(W,q)$ that share the same mismatch capacity. We prove that if the class contains a matched pair, then our bound is tight and the mismatch capacity of the entire class is fully characterized and is equal to the LM rate, which is achievable by random coding, and may be strictly lower that the matched capacity. [ABSTRACT FROM AUTHOR]

Graph convolutional networks (GCNs) are a widely used method for graph representation learning. To elucidate their capabilities and limitations for graph classification, we investigate their power to generate well-separated embedding vectors for graphs sampled from different random graph models, which correspond to different class-conditional distributions in a classification problem. It has been recognized that metric properties of learned representations are important for reduction of complexity of classifiers trained on them. Additionally, we show that inability to generate well-separated embedding vectors for two different graph models implies information-theoretic indistinguishability of these models based on noise-perturbed embedding vectors of sample graphs. We consider graph models arising from graphons, which parametrize all infinite exchangeable graph models. We precisely characterize, in terms of degree profile closeness, the set of graphon pairs that are indistinguishable (in metric and information-theoretic senses) by a GCN with depth at least logarithmic in sample graph size. Outside this set, a very simple architecture suffices for distinguishability. We then exhibit a concrete, infinite set of graphon pairs that are well-separated in cut distance and are indistinguishable by a GCN. These results theoretically match empirical observations of several prior works. Finally, we give empirical results on synthetic and real graph classification datasets, giving some indication that degree profile closeness gives rise to indistinguishability of graph distributions in real datasets, even beyond our theoretical framework. [ABSTRACT FROM AUTHOR]

We revise the proof of low-rate upper bounds on the reliability function of discrete memoryless channels for ordinary and list-decoding schemes, in particular Berlekamp and Blinovsky’s zero-rate bound, as well as Blahut’s bound for low rates. The available proofs of the zero-rate bound devised by Berlekamp and Blinovsky are somehow complicated in that they contain in one form or another some “non-standard” procedures or computations. Here we follow Blinovsky’s idea of using a Ramsey-theoretic result by Komlós, and we complement it with some missing steps to present a proof which is rigorous and easier to inspect. Furthermore, we show how these techniques can be used to fix an error that invalidated the proof of Blahut’s low-rate bound, which is here presented in an extended form for list decoding and for general channels. [ABSTRACT FROM AUTHOR]

We propose an information-theoretic bound on the generalization error based on a combination of the error decomposition technique of Bu et al. and the conditional mutual information (CMI) construction of Steinke and Zakynthinou. In a previous work, Haghifam et al. proposed a different bound combining the two aforementioned techniques, which we refer to as the conditional individual mutual information (CIMI) bound. However, in a simple Gaussian setting, both the CMI and the CIMI bounds are order-wise worse than that by Bu et al. This observation motivated us to propose the bound, which overcomes this issue by reducing the conditioning terms in the conditional mutual information. In the process of establishing this bound, a conditional decoupling lemma is established, which also leads to a meaningful dichotomy and comparison among these information-theoretic bounds. As an application of the proposed bound, we analyze the noisy and iterative stochastic gradient Langevin dynamics and provide an upper bound on its generalization error. [ABSTRACT FROM AUTHOR]

We study rates of asymptotic transformations between entangled states by local operations and classical communication and a sublinear amount of quantum communication. It is known that additive asymptotically continuous entanglement measures provide upper bounds on the rates that are achievable with asymptotically vanishing error. We show that for transformations between pure states, the optimal rate between any pair of states can be characterized as the infimum of such upper bounds provided by fully additive asymptotically continuous entanglement measures. [ABSTRACT FROM AUTHOR]

We study the entanglement dynamics of quantum many-body systems and prove the following: (I) For any geometrically local Hamiltonian on a lattice, starting from a random product state the entanglement entropy is bounded away from the maximum entropy at all times with high probability. (II) In a spin-glass model with random all-to-all interactions, starting from any product state the average entanglement entropy is bounded away from the maximum entropy at all times. We also extend these results to any unitary evolution with charge conservation and to the Sachdev-Ye-Kitaev model. Our results highlight the difference between the entanglement generated by (chaotic) Hamiltonian dynamics and that of random states, for the latter is nearly maximal. [ABSTRACT FROM AUTHOR]

We determine the exact value of the optimal symmetric rate point $(r, r)$ in the Dueck zero-error capacity region of the binary adder channel with complete feedback. We proved that the average zero-error capacity $r = h(1/2-\delta) \approx 0.78974$ , where $h(\cdot)$ is the binary entropy function and $\delta = 1/(2\log _{2}(2 + \sqrt {3}))$. Our motivation is a problem in quantitative group testing. Given a set of $n$ elements two of which are defective, the quantitative group testing problem asks for the identification of these two defectives through a series of tests. Each test gives the number of defectives contained in the tested subset, and the outcomes of previous tests are assumed known at the time of designing the current test. We establish that the minimum number of tests is asymptotic to $(\log _{2} n) / r$ as $n \to \infty $. [ABSTRACT FROM AUTHOR]

Sequences with low aperiodic autocorrelation and crosscorrelation are used in communications and remote sensing. Golay and Shapiro independently devised a recursive construction that produces families of complementary pairs of binary sequences. In the simplest case, the construction produces the Rudin–Shapiro sequences, and in general it produces what we call Golay–Rudin–Shapiro sequences. Calculations by Littlewood show that the Rudin–Shapiro sequences have low mean square autocorrelation. A sequence’s peak sidelobe level is its largest magnitude of autocorrelation over all nonzero shifts. Høholdt, Jensen, and Justesen showed that there is some undetermined positive constant $A$ such that the peak sidelobe level of a Rudin–Shapiro sequence of length $2^{n}$ is bounded above by $A(1.842626\ldots)^{n}$ , where $1.842626\ldots $ is the positive real root of $X^{4}-3 X-6$. We show that the peak sidelobe level is bounded above by $5(1.658967\ldots)^{n-4}$ , where $1.658967\ldots $ is the real root of $X^{3}+X^{2}-2 X-4$. Any exponential bound with lower base will fail to be true for almost all $n$ , and any bound with the same base but a lower constant prefactor will fail to be true for at least one $n$. We provide a similar bound on the peak crosscorrelation (largest magnitude of crosscorrelation over all shifts) between the sequences in each Rudin–Shapiro pair. The methods that we use generalize to all families of complementary pairs produced by the Golay–Rudin–Shapiro recursion, for which we obtain bounds on the peak sidelobe level and peak crosscorrelation with the same exponential growth rate as we obtain for the original Rudin–Shapiro sequences. [ABSTRACT FROM AUTHOR]

A secret-sharing scheme realizes the forbidden graph access structure determined by a graph $G=(V,E)$ if the parties are the vertices of the graph and the subsets that can reconstruct the secret are the pairs of vertices in $E$ (i.e., the edges) and the subsets of at least three vertices. Secret-sharing schemes for forbidden graph access structures defined by bipartite graphs are equivalent to conditional disclosure of secrets (CDS) protocols. We study the complexity of realizing a forbidden graph access structure by linear secret-sharing schemes, which are schemes in which the secret can be reconstructed from the shares by a linear mapping. We provide efficient constructions and lower bounds on the share size of linear secret-sharing schemes for sparse and very dense graphs, closing the gap between upper and lower bounds. Given a sparse (resp. very dense) graph with $n$ vertices and at most $n^{1+\beta }$ edges (resp. at least $\binom {n}{2} - n^{1+\beta }$ edges), for some $0 \leq \beta < 1$ , we construct a linear secret-sharing scheme realizing its forbidden graph access structure with total share size $\tilde {O} (n^{1+\beta /2})$. Furthermore, we construct linear secret-sharing schemes realizing these access structures in which the size of each share is $\tilde {O} (n^{1/4+\beta /4})$. We also provide constructions achieving different trade-offs between the size of each share and the total share size. We prove that almost all forbidden graph access structures require linear secret-sharing schemes with total share size $\Omega (n^{3/2})$ ; this shows that the construction of Gay, Kerenidis, and Wee [CRYPTO 2015] is optimal. Furthermore, we show that for every $0 \leq \beta < 1$ there exist a graph with at most $n^{1+\beta }$ edges and a graph with at least $\binom {n}{2}-n^{1+\beta }$ edges such that the total share size in any linear secret-sharing scheme realizing the associated forbidden graph access structures is $\Omega (n^{1+\beta /2})$. Finally, we show that for every $0 \leq \beta < 1$ there exist a graph with at most $n^{1+\beta }$ edges and a graph with at least $\binom {n}{2}-n^{1+\beta }$ edges such that the size of the share of at least one party in any linear secret-sharing scheme realizing these forbidden graph access structures is $\Omega (n^{1/4+\beta /4})$. This shows that our constructions are optimal (up to poly-logarithmic factors). [ABSTRACT FROM AUTHOR]

This study considers the unconditional smooth Rényi entropy proposed by Renner and Wolf [ASIACRYPT, 2005], the smooth conditional Rényi entropy proposed by Kuzuoka [IEEE Trans. Inf. Th., 66(3), 1674–1690, 2020], and a novel quantity which we term the conditional smooth-⋆ entropy. The latter two quantities can be specialized to the first in the absence of side-information. We explore the operational roles of these smooth Rényi entropies by establishing one-shot coding theorems for several information-theoretic problems, including Campbell’s source coding problem, the Arıkan–Massey guessing problem, and the Bunte–Lapidoth task encoding problem. We consider these problems in cases where the errors are non-vanishing and for each problem, we consider two error formalisms: the average and maximum error criteria, where the averaging and maximization are taken with respect to the side-information. Using the one-shot coding theorems, we conclude that Kuzuoka’s smooth conditional Rényi entropy and the conditional smooth-⋆ entropy are the solutions to the problems involving the average and maximum error criteria, respectively. Furthermore, we examine asymptotic expansions of these entropies when the underlying source with its side-information is stationary and memoryless. Applying our asymptotic expansions to the one-shot coding theorems, we derive various fundamental limits for these problems. We show that, under non-degenerate settings, the first-order fundamental limits differ under the average and maximum error criteria. This is in contrast to a different but related setting considered by the present authors [IEEE Trans. Inf. Th., 66(12), 7565–7587, 2020], for variable-length conditional source coding allowing errors, in which the first-order terms are identical but the second-order terms are different under these error criteria. [ABSTRACT FROM AUTHOR]

New asymptotic upper bounds are presented on the rate of sequences of locally repairable codes (LRCs) with a prescribed relative minimum distance and locality over a finite field $F$. The bounds apply to LRCs in which the recovery functions are linear; in particular, the bounds apply to linear LRCs over $F$. The new bounds are shown to improve on previously published results, especially when the repair groups are disjoint, namely, they form a partition of the set of coordinates. [ABSTRACT FROM AUTHOR]

We derive an upper bound on the reliability function of mismatched decoding for zero-rate codes. The bound is based on a result by Komlós that shows the existence of a subcode with certain symmetry properties. The bound is shown to coincide with the expurgated exponent at rate zero for a broad family of channel-decoding metric pairs. [ABSTRACT FROM AUTHOR]

A family of error-correcting codes is list-decodable from error fraction $p$ if, for every code in the family, the number of codewords in any Hamming ball of fractional radius $p$ is less than some integer $L$. It is said to be list-recoverable for input list size $\ell $ if for every sufficiently large subset of at least $L$ codewords, there is a coordinate where the codewords take more than $\ell $ values. In this work, we study the list size of random linear codes for both list-decoding and list-recovery as the rate approaches capacity. We show the following claims hold with high probability over the choice of the code (below $q$ is the alphabet size, and $ \varepsilon > 0$ is the gap to capacity). (1) A random linear code of rate $1 - \log _{q}(\ell) - \varepsilon $ requires list size $L \ge \ell ^{\Omega (1/ \varepsilon)}$ for list-recovery from input list size $\ell $. (2) A random linear code of rate $1 - h_{q}(p) - \varepsilon $ requires list size $L \ge \left \lfloor{ {h_{q}(p)/ \varepsilon +0.99}}\right \rfloor $ for list-decoding from error fraction $p$. (3) A random binary linear code of rate $1 - h_{2}(p) - \varepsilon $ is list-decodable from average error fraction $p$ with list size with $L \leq \left \lfloor{ {h_{2}(p)/ \varepsilon }}\right \rfloor + 2$. Our lower bounds follow by exhibiting an explicit subset of codewords so that this subset—or some symbol-wise permutation of it—lies in a random linear code with high probability. Our upper bound follows by strengthening a result of (Li, Wootters, 2018). [ABSTRACT FROM AUTHOR]

The trade-off between the two types of error probabilities in binary state discrimination may be quantified in the asymptotics by various error exponents. In the composite case, where the hypotheses consist of sets of states, any such exponent is upper bounded by the infimum of the corresponding pairwise exponents of discriminating individual members of the two sets. Attainability of this upper bound may depend on the type of exponents considered; whether the problem is classical or quantum; the cardinality and the geometric properties of the sets representing the hypotheses; and also on the dimensionality of the underlying Hilbert space. Our main contribution is clarifying this landscape considerably. We show that in the quantum case unattainability is the general behaviour for all the exponents, already in finite dimension, for a simple null-hypothesis and an alternative hypothesis consisting of only two states. Moreover, the upper bound may be strict even in the infinite-dimensional classical case if the alternative hypothesis contains at least countably infinitely many states. We also prove general attainability results, e.g., for classical adversarial and arbitrarily varying hypothesis testing, and for the quantum case where all states are pure, or the states commute with every state in the opposite hypothesis. [ABSTRACT FROM AUTHOR]

A flag of codes $C_{0} \subsetneq C_{1} \subsetneq \cdots \subsetneq C_{s} \subseteq \mathbb {F}_{q} ^{n}$ is said to satisfy the isometry-dual property if there exists ${\mathbf{x}}\in (\mathbb {F}_{q}^{*})^{n}$ such that the code $C_{i}$ is x-isometric to the dual code $C_{s-i}^\perp $ for all $i=0,\ldots, s$. For $P$ and $Q$ rational places in a function field $\mathcal {F}$ , we investigate the existence of isometry-dual flags of codes in the families of two-point algebraic geometry codes $C_{\mathcal {L}}(D, a_{0}P+bQ)\subsetneq C_{\mathcal {L}}(D, a_{1}P+bQ)\subsetneq {\dots } \subsetneq C_{\mathcal {L}}(D, a_{s}P+bQ)$ , where the divisor $D$ is the sum of pairwise different rational places of $\mathcal {F}$ and $P, Q$ are not in $\mathop {\mathrm {supp}}\nolimits (D)$. We characterize those sequences in terms of $b$ for general function fields. We then apply the result to the broad class of Kummer extensions $\mathcal {F}$ defined by affine equations of the form $y^{m}=f(x)$ , for $f(x)$ a separable polynomial of degree $r$ , where $\gcd (r, m)=1$. For $P$ the rational place at infinity and $Q$ the rational place associated to one of the roots of $f(x)$ , and for $D$ an $Aut(\mathcal {F}/ \mathbb {F}_{q})$ -invariant sum of rational places of $\mathcal {F}$ , such that $P, Q \notin \mathop {\mathrm {supp}}\nolimits D$ , it is shown that the flag of two-point algebraic geometry codes has the isometry-dual property if and only if $m$ divides $2b+1$. At the end we illustrate our results by applying them to two-point codes over several well know function fields. [ABSTRACT FROM AUTHOR]

We present methods for computing the distance from a Boolean polynomial on $m$ variables of degree $m-3$ (i.e., a member of the Reed–Muller code $RM(m-3, m)$) to the space of lower-degree polynomials ($RM(m-4, m)$). The methods give verifiable certificates for both the lower and upper bounds on this distance. By applying these methods to representative lists of polynomials, we show that the covering radius of $RM(4,8)$ in $RM(5,8)$ is 26 and the covering radius of $RM(5,9)$ in $RM(6,9)$ is between 28 and 32 inclusive, and we get improved lower bounds for higher $m$. We also apply our methods to various polynomials in the literature, thereby improving the known bounds on the distance from 2-resilient polynomials to $RM(m-4, m)$. [ABSTRACT FROM AUTHOR]

Multipartite secret sharing schemes are those having a multipartite access structure, in which the set of participants is divided into several parts and all participants in the same part play an equivalent role. Secret sharing schemes for multipartite access structures have received considerable attention due to the fact that multipartite secret sharing can be seen as a natural and useful generalization of threshold secret sharing. This work deals with efficient and explicit constructions of ideal multipartite secret sharing schemes. Most ideal multipartite secret sharing schemes in the literature can be classified as either hierarchical or compartmented. The main results are the constructions for ideal hierarchical access structures, a family that contains every ideal hierarchical access structure as a particular case such as the disjunctive hierarchical threshold access structure and the conjunctive hierarchical threshold access structure, the constructions for three families of compartmented access structures, and the constructions for two families compartmented access structures with compartments. We present an efficient method to construct ideal linear schemes realizing these access structures by linear algebraic techniques on the basis of the relationship between multipartite secret sharing schemes, polymatroids and matroids. [ABSTRACT FROM AUTHOR]

Error-correcting codes over sets, with applications to DNA storage, are studied. The DNA-storage channel receives a set of sequences, and produces a corrupted version of the set, including sequence loss, symbol substitution, symbol insertion/deletion, and limited-magnitude errors in symbols. Various parameter regimes are studied. New bounds on code parameters are provided, which improve upon known bounds. New codes are constructed, at times matching the bounds up to lower-order terms or small constant factors. [ABSTRACT FROM AUTHOR]

Let $\mathcal {X}= \{x_{1},x_{2},\ldots, x_{q}\}$ and let $n(m,q,\ell)$ be the smallest $n$ for which there is a code $C \subseteq \mathcal {X} ^{n}$ of $m$ elements such that for every list $w_{1}, w_{2}, \ldots, w_{\ell +1}$ of distinct codewords from $C$ , there is a coordinate $j \in [n]$ such that $\{w_{1}[j], w_{2}[j], \ldots, w_{\ell +1}[j]\} = \mathcal {X}$. We show that there is a constant $A>0$ such that for $\epsilon < 1/5$ , for all large $q$ and large enough $m$ ($m>q^{5}$), we have $n(m,q, \lceil \epsilon q\ln {q}\rceil) \geq \exp {(Aq^{1-5\epsilon })}\log _{2}{m}$. This bound has consequences for the zero-error list-decoding capacity of the $q/(q-1)$ channel studied by Elias (1988). Our result implies that for $A$ and $\epsilon $ as above, the zero-error list-decoding capacity of the $q/(q-1)$ channel with list-size $\epsilon q\ln {q}$ is at most $\exp (-Aq^{1-5\epsilon })$ , that is, it falls exponentially as $q$ increases. This confirms a conjecture of Chakraborty et al. (2006). [ABSTRACT FROM AUTHOR]

Novel bounds on the left- and right-tail probability of the Binomial distribution are presented. Specifically, bounds on the left-tail probability $\text {P}\!\left [{S_{n}\leqslant an}\right]$ with $a\in (0,p)$ and the right-tail probability $\text {P}\!\left [{S_{n}\geqslant an}\right]$ with $a\in (p,1)$ , where $S_{n}$ follows the Binomial law with parameters $n\geqslant 1$ and $p\in (0,1)$ , are derived. The bounds are tighter than the best known closed-form expressions. The presented upper and lower bounds on the right-tail match an asymptotic expansion of $\log \text {P}\!\left [{S_{n}\geqslant na}\right]$ up to, and including, the $\log n$ term. In particular, the ratio between the upper and lower bounds is $1/(1-c/n)$ , where $c$ is independent of $n$. Similar results are presented for the left-tail probability. Applications to finite blocklength source and channel coding are presented. [ABSTRACT FROM AUTHOR]