In this paper, we consider a concatenated coding based class of DNA storage codes in which the selected molecules are constrained to be taken from an "inner" codebook associated with the sequencing channel. This codebook is used in a "black-box" manner, and is only assumed to operate at an achievable rate in the sense of attaining asymptotically vanishing maximal (inner) error probability. We first derive the exact error exponent in a widely-studied regime of constant rate and a linear number of sequencing reads, and show strict improvements over an existing achievable error exponent. Moreover, our achievability analysis is based on a coded-index strategy, implying that such strategies attain the highest error exponents within the broader class of codes that we consider. We then extend our results to other scaling regimes, including a super-linear number of reads, as well as several low-rate regimes. We find that the latter comes with notable intricacies, such as dependencies of the error exponents on the model for sequencing errors.

In this paper, we consider a concatenated coding based class of DNA storage codes in which the selected molecules are constrained to be taken from an “inner” codebook associated with the sequencing channel. This codebook is used in a “black-box” manner, and is only assumed to operate at an achievable rate in the sense of attaining asymptotically vanishing maximal (inner) error probability. We derive the exact error exponent for this class of codes under widely-adopted parameter scalings, with strict improvements over an existing achievable error exponent. Moreover, our achievability analysis is based on a coded-index strategy, implying that such strategies attain the highest error exponents within the broader class of codes that we consider.

We study error exponents for the problem of low-rate communication over a directed graph, where each edge in the graph represents a noisy communication channel, and there is a single source and destination. We derive maxflow-based achievability and converse bounds on the error exponent that match when there are two messages and all channels satisfy a symmetry condition called pairwise reversibility. More generally, we show that the upper and lower bounds match to within a factor of 4. We also show that with three messages there are cases where the maxflow-based error exponent is strictly suboptimal, thus showing that our tightness result cannot be extended beyond two messages without further assumptions.

In this paper, we study the problem of relaying a single bit over a tandem of binary-input channels, with the goal of attaining the highest possible error exponent in the exponentially decaying error probability. Our previous work gave an exact characterization of the best possible error exponent in various special cases, including when the two channels are identical, but the general case was left as an open problem. We resolve this open problem by deriving a new converse bound that matches our existing achievability bound.

In this paper, we consider a bandit problem in which there are a number of groups each consisting of infinitely many arms. Whenever a new arm is requested from a given group, its mean reward is drawn from an unknown reservoir distribution (different for each group), and the uncertainty in the arm’s mean reward can only be reduced via subsequent pulls of the arm. The goal is to identify the infinite-arm group whose reservoir distribution has the highest $(1-\alpha)$-quantile (e.g., median if $\alpha = \frac{1}{2}$), using as few total arm pulls as possible. We introduce a two-step algorithm that first requests a fixed number of arms from each group and then runs a finite-arm grouped max-quantile bandit algorithm. We characterize both the instance-dependent and worst-case regret, and provide a matching lower bound for the latter, while discussing various strengths, weaknesses, algorithmic improvements, and potential lower bounds associated with our instance-dependent upper bounds.

We study error exponents for the problem of relaying a message over a tandem of two channels sharing the same transition law, in particular moving beyond the 1-bit setting studied in recent related works. Our main results show that the 1-hop and 2-hop exponents coincide in both of the following settings: (i) the number of messages is fixed, and the channel law satisfies a condition called pairwise reversibility, or (ii) the channel is arbitrary, and a zero-rate limit is taken from above. In addition, we provide various extensions of our results that relax the assumptions of pairwise reversibility and/or the two channels having identical transition laws, and we provide an example for which the 2-hop exponent is strictly below the 1-hop exponent.

In this paper, we study the problem of relaying a single bit of information across a series of binary symmetric channels, and the associated trade-off between the number of hops m, the transmission time n, and the error probability. We introduce a simple, efficient, and deterministic protocol that attains positive information velocity (i.e., a non-vanishing ratio $\frac{m}{n}$ and small error probability) and is significantly simpler than existing protocols that do so. In addition, we characterize the optimal low-noise and high-noise scaling laws of the information velocity, and we adapt our 1-bit protocol to transmit k bits over m hops with ${\mathcal{O}}(m + k)$ transmission time.

In this paper, we study the problem of relaying a single bit of information across a series of binary symmetric channels, and the associated trade-off between the number of hops$m$, the transmission time$n$, and the error probability. We introduce a simple, efficient, and deterministic protocol that attains positive information velocity (i.e., a non-vanishing ratio$\frac {m}{n}$and small error probability) and is significantly simpler than existing protocols that do so. In addition, we characterize the optimal low-noise and high-noise scaling laws of the information velocity, and we adapt our 1-bit protocol to transmit$k$bits over$m$hops with$\mathcal {O}(m+k)$transmission time.

In this paper, we consider a recently-proposed model of teaching and learning under uncertainty, in which a teacher receives independent observations of a single bit corrupted by binary symmetric noise, and sequentially transmits to a student through another binary symmetric channel based on the bits observed so far. After a given number$n$of transmissions, the student outputs an estimate of the unknown bit, and we are interested in the exponential decay rate of the error probability as$n$increases. We propose a novel block-structured teaching strategy in which the teacher encodes the number of 1s received in each block, and show that the resulting error exponent is the binary relative entropy$D(\frac{1}{2}\Vert\max(p,\ q))$, where$p$and$q$are the noise parameters. This matches a trivial converse result based on the data processing inequality, and settles two conjectures of [Jog and Loh, 2021] and [Huleihel et al., 2019]. In addition, we show that the computation time required by the teacher and student is linear in n.

In this paper, we consider a recently-proposed model of teaching and learning under uncertainty, in which a teacher receives independent observations of a single bit corrupted by binary symmetric noise, and sequentially transmits to a student through another binary symmetric channel based on the bits observed so far. After a given number$n$of transmissions, the student outputs an estimate of the unknown bit, and we are interested in the exponential decay rate of the error probability as$n$increases. We propose a novel block-structured teaching strategy in which the teacher encodes the number of 1s received in each block, and show that the resulting error exponent is the binary relative entropy$D\left({\frac {1}{2}\|\max (p,q)}\right)$, where$p$and$q$are the noise parameters. This matches a trivial converse result based on the data processing inequality, and settles two conjectures of [Jog and Loh, 2021] and [Huleihelet al., 2019]. In addition, we show that the computation time required by the teacher and student is linear in$n$. We also study a more general setting in which the binary symmetric channels are replaced by general binary-input discrete memoryless channels. We provide an achievability bound and a converse bound, and show that the two coincide in certain cases, including (i) when the two channels are identical, and (ii) when the student-teacher channel is a binary symmetric channel. More generally, we give sufficient conditions under which our learning rate is the best possible for block-structured protocols.