Robust Gray codes were introduced by (Lolck and Pagh, SODA 2024). Informally, a robust Gray code is a (binary) Gray code $\mathcal{G}$ so that, given a noisy version of the encoding $\mathcal{G}(j)$ of an integer $j$, one can recover $\hat{j}$ that is close to $j$ (with high probability over the noise). Such codes have found applications in differential privacy. In this work, we present near-optimal constructions of robust Gray codes. In more detail, we construct a Gray code $\mathcal{G}$ of rate $1 - H_2(p) - \varepsilon$ that is efficiently encodable, and that is robust in the following sense. Supposed that $\mathcal{G}(j)$ is passed through the binary symmetric channel $\text{BSC}_p$ with cross-over probability $p$, to obtain $x$. We present an efficient decoding algorithm that, given $x$, returns an estimate $\hat{j}$ so that $|j - \hat{j}|$ is small with high probability.

In array-based DNA synthesis, multiple strands of DNA are synthesized in parallel to reduce the time cost from the sum of their lengths to the length their shortest common supersequences. To maximize the amount of information that can be synthesized into DNA within a finite amount of time, we study the number of unordered sets of$n$strands of DNA that have a common supersequence whose length is at most$t$. Our analysis stems from the following connection: The number of subsequences of A C G T A C G T A C G T … is the partial sum (prefix sum) of the fourth-order Fibonacci numbers.

Successive cancellation list (SCL) decoders of polar codes excel in practical performance but pose challenges for theoretical analysis. Existing works either limit their scope to erasure channels or address general channels without taking advantage of soft information. In this paper, we propose the successive cancellation sampling (SCS) decoder. SCS hires iid “agents” to sample codewords using posterior probabilities. This makes it fully parallel and amenable for some theoretical analysis. As an example, when comparing SCS with$\boldsymbol{a}$agents to any list decoder with list size$\boldsymbol{\ell}$, we can prove that the error probability of the former is at most$\boldsymbol{\ell}/\boldsymbol{ae}$more than that of the latter. In this paper, we also describe how to adjust the “temperature” of agents. Warmer agents are less likely to sample the same codewords and hence can further reduce error probability.

Group testing (GT) is the art of identifying binary signals and the marketplace for exchanging new ideas for related fields such as unique-element counting, compressed sensing, traitor tracing, and geno-typing. A GT scheme can be nonadaptive or adaptive; the latter is preferred when latency is ess of an issue. To construct adaptive GT schemes, a popular strategy is to spend the majority of tests in the first few rounds to gain as much information as possible, and uses later rounds to refine details. In this paper, we propose a transparent strategy called isolate and then identify (I@I). In the first few rounds, I@I divides the population into teams until every team contains at most one sick person. Then, in the last round, I@I identifies the sick person in each team. Performance-wise, I@I is the first GT scheme that achieves the optimal coefficient 1/capacity(Z) for the$k\log_{2}(n/k)$term in the number of tests when$\boldsymbol{Z}$is a generic channel corrupting the test outcomes. I@I follows a modular methodology whereby the isolating part and the identification part can be optimized separately.

We prove $1 - {\left( {1 - {x^M}} \right)^{{2^M}}} > {\left( {1 - {{(1 - x)}^M}} \right)^{{2^M}}}$ for all x ∈ [0, 1] and all M > 1. This confirms a conjecture about polar code, made by Wu and Siegel in 2019, that ${W^{{0^m}{1^M}}}$ is more reliable than ${W^{{1^m}}}{0^M}$, where W is any binary erasure channel and M = 2m. The proof relies on a relaxation that m needs not be an integer, the solvability of a hexavariate ordinary differential equation, and a generalization of Green’s theorem that concerns function composition. The resulting inequality is optimal, M cannot be 2m− 1, witnessing how far polar code deviates from Reed–Muller code.

Constructing a polar code is all about selecting a subset of rows from a Kronecker power of $ \left[ {\begin{array}{c} {10} \\ {11} \end{array}} \right] $. It is known that, under successive cancellation decoder, some rows are Paretobetter than the other. For instance, whenever a user sees a substring 01 in the binary expansion of a row index and replaces it with 10, the user obtains a row index that is always more welcomed. We call this a "rule" and denote it by 10 ≽ 01. In present work, we first enumerate some rules over binary erasure channels such as 1001 ≽ 0110 and 10001 ≽ 01010 and 10101 ≽ 01110. We then summarize them using a "rule of rules": if 10a ≽ 01b is a rule, where a and b are arbitrary binary strings, then 100a ≽ 010b and 101a ≽ 011b are rules. This work’s main contribution is using field theory, Galois theory, and numerical analysis to develop an algorithm that decides if a rule of rules is mathematically sound. We apply the algorithm to enumerate some rules of rules. Each rule of rule is capable of generating an infinite family of rules. For instance, 10c01 ≽ 01c10 for arbitrary binary string c can be generated. We found an application of 10c01 ≽ 01c10 that is related to integer partition and the dominance order therein.

We gather existing methods that are used to compare and rank the BECs synthesized by a polar code constructor, compare them, and propose new methods that compare synthetic BECs more quickly.

Polar codes that approach capacity at a near-optimal speed, namely with scaling exponents close to 2, have been shown possible for q-ary erasure channels (Pfister and Urbanke), the BEC (Fazeli, Hassani, Mondelli, and Vardy), all BMS channels (Guruswami, Riazanov, and Ye), and all DMCs (Wang and Duursma). There is, nevertheless, a subtlety separating the last two papers from the first two, namely the usage of multiple dynamic kernels in the polarization process, which leads to increased complexity and fewer opportunities to hardware-accelerate. This paper clarifies this subtlety, providing a tradeoff between the number of kernels in the construction and the scaling exponent. We show that the number of kernels can be bounded by O(ℓ3/µ−1) where µ is the targeted scaling exponent and ℓ is the kernel size. In particular, if one settles for scaling exponent approaching 3, a single kernel suffices, and to approach the optimal scaling exponent of 2, about $O(\sqrt \ell )$ kernels suffice.

We modify Price and Scarlett’s fast binary splitting approach to nonadaptive group testing [1]. We show that, to identify a uniformly random subset of k infected persons among a population of n, it takes only ln(2−4ε)−2k ln n tests and decoding complexity O(ε−2k ln n), for any small ε > 0, with vanishing error probability. In works prior to ours, only two types of group testing schemes exist. Those that use ln(2)−2k ln n or fewer tests require linear-in-n complexity, sometimes even polynomial in n; those that enjoy sub-n complexity employ O(k ln n) tests, where the big-O scalar is implicit, presumably greater than ln(2)−2. We almost achieve the best of both worlds, namely, the almost-ln(2)−2scalar and the sub-n decoding complexity. How much further one can reduce the scalar ln(2)−2remains an open problem.

Polymerase chain reaction (PCR) testing is the gold standard for diagnosing COVID-19. PCR amplifies the virus DNA 40 times to produce measurements of viral loads that span seven orders of magnitude. Unfortunately, the outputs of these tests are imprecise and therefore quantitative group testing methods, which rely on precise measurements, are not applicable. Motivated by the ever-increasing demand to identify individuals infected with SARS-CoV-19, we propose a new model that leverages tropical arithmetic to characterize the PCR testing process. Our proposed framework, termed tropical group testing, overcomes existing limitations of quantitative group testing by allowing for imprecise test measurements. In many cases, some of which are highlighted in this work, tropical group testing is provably more powerful than traditional binary group testing in that it requires fewer tests than classical approaches, while additionally providing a mechanism to identify the viral load of each infected individual. It is also empirically stronger than related works that have attempted to combine PCR, quantitative group testing, and compressed sensing.

Polar codes approach channel capacity provably and empirically and are thereby a constituent code of the 5G standard. Compared to low-density parity-check codes, however, the performance of short-length polar codes have rooms for improvement that could hinder its adoption by a wider class of applications. As part of the program that addresses the performance issue at short length, it is crucial to understand how fast binary memoryless symmetric channels polarize. A number, called scaling exponent, was defined to measure the speed of polarization and several estimates of the scaling exponent were given in literature. As of 2022, the tightest overestimate is 4.714 made by Mondelli, Hassani, and Urbanke in 2015. We lower the overestimate to 4.63. The idea behind this improvement is that, instead of describing the relation between a channel${W}$and its children${W}^ {\scriptscriptstyle {\boxed {\star}}}$and${W}^ {\bigcirc \!\!\! \star}$, we describe the relation between${W}$and its grandchildren$ {W}^{\scriptscriptstyle {\boxed {\star}} \, {\scriptscriptstyle {\boxed {\star}}} }$,${W}^{\scriptscriptstyle {\boxed {\star}}\, {{\bigcirc \!\! \star} }}$,${W}^{{\bigcirc \!\!\! \star}\,\,{\scriptscriptstyle {\boxed {\star}}} }$, and$ {W}^{{\bigcirc \!\!\! \star}\,{\bigcirc \!\!\! \star} }$. By doing so, the evolution of channels becomes “less Markovian” and hence more tighter inequalities can be obtained.

Polarization is an unprecedented coding technique in that it not only achieves channel capacity, but also does so at a faster speed of convergence than any other technique. This speed is measured by the "scaling exponent" and its importance is three-fold. Firstly, estimating the scaling exponent is challenging and demands a deeper understanding of the dynamics of communication channels. Secondly, scaling exponents serve as a benchmark for different variants of polar codes that helps us select the proper variant for real-life applications. Thirdly, the need to optimize for the scaling exponent sheds light on how to reinforce the design of polar code. In this paper, we generalize the binary erasure channel (BEC), the simplest communication channel and the protagonist of many polar code studies, to the "tetrahedral erasure channel" (TEC). We then invoke Mori-Tanaka’s 2 × 2 matrix over 𝔽_4 to construct polar codes over TEC. Our main contribution is showing that the dynamic of TECs converges to an almost-one-parameter family of channels, which then leads to an upper bound of 3.328 on the scaling exponent. This is the first non-binary matrix whose scaling exponent is upper-bounded. It also polarizes BEC faster than all known binary matrices up to 23 × 23 in size. Our result indicates that expanding the alphabet is a more effective and practical alternative to enlarging the matrix in order to achieve faster polarization.

Polymerase chain reaction (PCR) testing is the gold standard for diagnosing COVID-19. Unfortunately, the outputs of these tests are imprecise and therefore quantitative group testing methods, which rely on precise measurements, are not applicable. Motivated by the ever-increasing demand to identify individuals infected with SARS-CoV-19, we propose a new model that leverages tropical arithmetic to characterize the PCR testing process. In many cases, some of which are highlighted in this work, tropical group testing is provably more powerful than traditional binary group testing in that it requires fewer tests than classical approaches, while additionally providing a mechanism to identify the viral load of each infected individual.

Over any discrete memoryless channel, we offer error correction codes such that: for one, their block error probabilities and code rates scale like random codes'; and for two, their encoding and decoding complexities scale like polar codes'. Quantitatively, for any constants π, ρ > 0 π +2ρπ) , code rate N-ρless than the Shannon capacity, and encoding and decoding complexity O(N log N}) per code block. The core theme is to incorporate polar coding (which limits the complexity to polar's realm) with large, random, dynamic kernels (which boosts the performance to random's realm). The putative codes are optimal in the following manner: Should π +2ρ>1 , no such codes exist over generic channels regardless of complexity.

A pruned variant of polar coding is proposed for binary erasure channel (BEC). Fix any BEC. For sufficiently small ε > 0, we construct a series of capacity achieving codes with block length N = ε-4.9, code rate R = Capacity - O(ε), block error probability P = ε, and encoding and decoding time complexity bC = O(log|log ε|) per information bit. The given per-bit complexity bC is log-logarithmic in N, in Capacity - R, and in P. Beyond BEC, there is a generalization: Fix a prime q and fix a symmetric, q-ary-input, discrete-output memoryless channel. For sufficiently small ε > 0, we construct a series of error correction codes with block length N = ε-constant, code rate R = Capacity - O(ε), block error probability P = ε, and encoding and decoding time complexity bC = O(log|log ε|) per information bit. Over general channels, this family of codes has the lowest per-bit time complexity among all capacity-achieving codes known to date.