Frameproof codes are a class of secure codes that were originally introduced in the pioneering work of Boneh and Shaw in the context of digital fingerprinting. They can be used to enhance the security and credibility of digital contents. LetMc,l(q)denote the largest cardinality of a q-ary c-frameproof code with length l. Based on an intriguing observation that relatesMc,l(q)to the renowned Erdős Matching Conjecture in extremal set theory, in 2003, Blackburn posed an open problem on the precise value of the limitRc,l= limq→∞Mc,l(q)/q⌈l/c⌉. By combining several ideas from the probabilistic method, we present a lower bound forMc,l(q), which, together with an upper bound of Blackburn, completely determinesRc,lforallfixedc, l, and resolves the above open problem in the full generality. We also present an improved upper bound forMc,l(q).

Motivated by applications in DNA-based data storage, constrained codes have attracted a considerable amount of attention from both academia and industry. We study the maximum cardinality of constrained codes for which the constraints can be characterized by a set of forbidden substrings, where by a substring we mean some consecutive coordinates in a string. The study of finite-type constrained codes, for which the set of forbidden substrings is finite, dated back to a pioneering and influential work of Shannon in the 1940s. To the best of our knowledge, for roughly 80 years, people have known essentially only one method, i.e., the “spectral method”, that computes the rate and the cardinality of finite-type constrained codes. We show that there is a surprisingly powerful method arising from enumerative combinatorics, which applies the Goulden-Jackson cluster theorem (previously not known to the coding community), that serves as an alternative method to compute the code rate and the exact cardinality of each fixed length, of these codes. Moreover, the computation can be done by solving a system of linear equations of size equal to the number of constraints, and the time complexity improves that of the spectral method when the number of constraints is relatively small. More interestingly, our new method has the flexibility that it also applies to constrained codes defined by an infinite number of forbidden substrings. As an example, variable-length non-overlapping codes have potential applications in DNA storage. Bilotta, also Wang and Wang asked for an explicit upper bound on the maximum cardinality of these codes. By applying the cluster method in concert with other tools in analytic combinatorics, we obtain such a bound, thereby giving an affirmative answer to their question. Moreover, our bound is tight when the code length divides the alphabet size, as shown by a construction of Blackburn. Lastly, we show that the spectral method and the cluster method are inherently related by establishing a direct connection between the spectral radius of the de Brujin graph used in the former and the convergence radius of the generating function used in the latter.

Tanner codes are error-correcting codes built from a bipartite graphGand a short inner codeC0. Expander codes are a special type of Tanner code, where the graph is highly interconnected, ensuring stronger error correction capabilities. This paper is motivated by the following natural and fundamental problem in decoding expander codes: What are the sufficient and necessary conditions that δ ∈ [0, 1] andd0∈ N must satisfy, so thateverybipartite expanderGwith vertex expansion ratio δ andeverylinear inner codeC0with minimum distanced0together define an expander code that corrects Ω(n) errors inO(n) time? ForC0being the parity-check code, the landmark work of Sipser and Spielman (IEEE-TIT’96) showed that δ > 3/4 is sufficient; later, Viderman (ACM-TOCT’13) improved this to δ > 2/3 - Ω(1) and he also showed that δ > 1/2 is necessary. For general linear codeC0, the previously best-known result of Dowling and Gao (IEEE-TIT’18) showed thatd0= Ω(cδ-2) is sufficient, wherecis the left-degree ofG. We present a near-optimal solution to the above problem for generalC0by showing that δd0> 3 is sufficient and δd0> 1 is necessary, thereby significantly improving Dowling-Gao’s result. To prove the sufficient condition, we present two novel algorithms for decoding arbitrary expander codes withδd0> 3, where the first algorithm is deterministic, and the second one is randomized and has a larger decoding radius. To prove the necessary condition, we generalize the aforementioned necessary result of Viderman, and construct for every pair of δ,d0with δd0=1, an expander code with constant distance, that only corrects a constant number of errors.

Tanner codes are graph-based linear codes whose parity-check matrices can be characterized by a bipartite graph $G$ together with a linear inner code $C_0$. Expander codes are Tanner codes whose defining bipartite graph $G$ has good expansion property. This paper is motivated by the following natural and fundamental problem in decoding expander codes: What are the sufficient and necessary conditions that $δ$ and $d_0$ must satisfy, so that \textit{every} bipartite expander $G$ with vertex expansion ratio $δ$ and \textit{every} linear inner code $C_0$ with minimum distance $d_0$ together define an expander code that corrects $Ω(n)$ errors in $O(n)$ time? For $C_0$ being the parity-check code, the landmark work of Sipser and Spielman (IEEE-TIT'96) showed that $δ>3/4$ is sufficient; later Viderman (ACM-TOCT'13) improved this to $δ>2/3-Ω(1)$ and he also showed that $δ>1/2$ is necessary. For general linear code $C_0$, the previously best-known result of Dowling and Gao (IEEE-TIT'18) showed that $d_0=Ω(cδ^{-2})$ is sufficient, where $c$ is the left-degree of $G$. In this paper, we give a near-optimal solution to the above question for general $C_0$ by showing that $δd_0>3$ is sufficient and $δd_0>1$ is necessary, thereby also significantly improving Dowling-Gao's result. We present two novel algorithms for decoding expander codes, where the first algorithm is deterministic, and the second one is randomized and has a larger decoding radius.

We establish a novel connection between the well-known chromatic threshold problem in extremal combinatorics and the celebrated (p, q)-theorem in discrete geometry. In particular, for a graph G with bounded clique number and a natural density condition, we prove a (p, q)-theorem for an abstract convexity space associated with G. Our result strengthens those of Thomassen and Nikiforov on the chromatic threshold of cliques. Our (p, q)-theorem can also be viewed as a χ-boundedness result for (what we call) ultra maximal Kr-free graphs. We further show that the graphs under study are blow-ups of constant size graphs, improving a result of Oberkampf and Schacht on homomorphism threshold of cliques. Our result unravels the cause underpinning such a blow-up phenomenon, differentiating the chromatic and homomorphism threshold problems for cliques. Our result implies that for the homomorphism threshold problem, rather than the minimum degree condition usually considered in the literature, the decisive factor is a clique density condition on co-neighborhoods of vertices. More precisely, we show that if an n-vertex Kr-free graph G satisfies that the common neighborhood of every pair of non-adjacent vertices induces a subgraph with Kr−2-density at least ε > 0, then G must be a blow-up of some Kr-free graph F on at most 2 O(rε log 1ε ) vertices. Furthermore, this single exponential bound is optimal.

Constant weight codes (CWCs) and constant compo-sition codes (CCCs) are two important classes of codes that have been extensively studied in the fields of combinatorics and coding theory for nearly 60 years. In this paper, we demonstrate that for all fixed odd distance, there are near-optimal CWCs and CCCs asymptotically achieving the classic Johnson-type upper bounds. Let$A_{q}(n,\ d,\ w)$denote the maximum size of q-ary CWCs of length$n$with constant weight$w$and minimum distance$d$. One of our main results shows that for all fixed$q, w$and odd$d$, we have$\displaystyle \lim_{n\rightarrow\infty}\frac{A_{q}(n,d,w)}{(_{t}^{n})}=\frac{(q-1)^{t}}{(_{t}^{w})}$, where$t=\displaystyle \frac{2w-d+1}{2}$. This implies the existence of near-optimal generalized Steiner systems originally introduced by Etzion. It can also be viewed as a counterpart of a celebrated result of Rödl on the existence of near-optimal Steiner systems. Note that prior to our work, very little is known about$A_{q}(n,\ w,\ d)$for$q\geq 3$. A similar result is proved for the maximum size of CCCs. We provide different proofs for our two main results, based on two strengthenings of the well-known Frankl-Rödl-Pippenger theorem on the existence of near-optimal matchings in hyper-graphs: the first proof follows by Kahn's linear programming variation of the above theorem, and the second follows by the recent independent work of Delcourt-Postle, and Glock-Joos-Kim-Kühn-Lichev on the existence of near-optimal matchings avoiding certain forbidden configurations. A full version of this paper can be found in [1].

Abstract. This paper shows that there exist Reed–Solomon (RS) codes, over exponentially large finite fields in the code length, that are combinatorially list-decodable well beyond the Johnson radius, in fact almost achieving the list-decoding capacity. In particular, we show that for any [Formula: see text] there exist RS codes with rate [Formula: see text] that are list-decodable from radius of [Formula: see text]. We generalize this result to list-recovery, showing that there exist [Formula: see text]-list-recoverable RS codes with rate [Formula: see text]. Along the way we use our techniques to give a new proof of a result of Blackburn on optimal linear perfect hash matrices, and strengthen it to obtain a construction of strongly perfect hash matrices. To derive the results in this paper we show a surprising connection of the above problems to graph theory, and in particular to the tree packing theorem of Nash-Williams and Tutte. We also state a new conjecture that generalizes the tree packing theorem to hypergraphs and show that if this conjecture holds, then there would exist RS codes that are optimally (nonasymptotically) list-decodable.

Abstract. In this paper we take a combinatorial approach to the problem of list-decoding, which allows us to determine the precise relation (up to the exact constant) between the decoding radius, list size, and code rate. We prove a generalized Singleton bound for a given list size, and conjecture that the bound is tight for most Reed–Solomon (RS) codes over large enough finite fields. We also show that the conjecture holds true for list sizes 2 and 3, and as a by product show that most RS codes with a rate of at least 1/9 are list-decodable beyond the Johnson radius. Last, we give the first explicit construction in the literature of such RS codes. The main tools used in the proof are a new type of linear dependency between codewords of a code that are contained in a small Hamming ball, and a surprising connection between list-decoding and the notion of cycle space in graph theory. Both of them are new, and may be of independent interest.

Abstract. For fixed integers [Formula: see text], and [Formula: see text], let [Formula: see text] denote the maximum number of edges in an [Formula: see text]-vertex [Formula: see text]-uniform hypergraph in which the union of arbitrary [Formula: see text] distinct edges contains at least [Formula: see text] vertices. In 1973, Brown, Erdős, and Sós proved that [Formula: see text] and conjectured that the limit [Formula: see text] always exists for all fixed integers [Formula: see text]. In 2020, Shangguan and Tamo conjectured that the limit [Formula: see text] always exists for all fixed integers [Formula: see text] and [Formula: see text], which contains the Brown–Erdős–Sós (BES) conjecture as a special case for [Formula: see text]. Recently, based on a result of Glock, Joos, Kim, Kühn, Lichev, and Pikhurko, Delcourt and Postle proved the BES conjecture. Extending their result, we show that the limit [Formula: see text] always exists, thereby resolving the BES problem for every uniformity.

Understanding the limits of list-decoding and list-recovery of Reed-Solomon (RS) codes is of prime interest in coding theory and has attracted a lot of attention in recent decades. However, the best possible parameters for these problems are still unknown, and in this paper, we take a step in this direction. We show the existence of RS codes that are list-decodable or list-recoverable beyond the Johnson radius foreveryrate, with a polynomial field size in the block length. In particular, we show that for every$\epsilon \in (0,1)$there exist RS codes that are list-decodable from radius$1-\epsilon $and rate less than$\frac {\epsilon }{2-\epsilon }$, with constant list size. We deduce our results by extending and strengthening a recent result of Ferber, Kwan, and Sauermann on puncturing codes with large minimum distance and by utilizing the underlying code’s linearity.

Hopping cyclic codes (HCCs) are (non-linear) cyclic codes with the additional property that the$n$cyclic shifts of every given codeword are all distinct, where$n$is the code length. Optical orthogonal codes (OOCs) are constructed from constant weight binary HCCs by picking exactly one member from the$n$cyclic shifts of every codeword. HCCs and OOCs have various practical applications and have been studied extensively over the years. In this paper, we present improved Gilbert-Varshamov type lower bounds on the size of both codes, when the minimum distance is bounded below by a linear factor of the code length. For HCCs, we improve the previously best known lower bound of Niu, Xing, and Yuan by a multiplicative linear factor of the code length. For OOCs, we improve the previously best known lower bound of Chung, Salehi, and Wei, and Yang and Fuja also by a multiplicative linear factor of the code length. Our proofs are based on tools from probability theory and graph theory, in particular the McDiarmid’s inequality on the concentration of Lipschitz functions and the independence number of locally sparse graphs.

This paper shows that there exist Reed-Solomon (RS) codes, over large finite fields, that are combinatorially list-decodable well beyond the Johnson radius, in fact almost achieving list-decoding capacity. In particular, we show that for any ε E (0,1] there exist RS codes with rate$\Omega(\frac{\varepsilon}{1\not\varepsilon(1/_{\in})+1})$that are list-decodable from radius of 1-ε. We generalize this result to list-recovery, showing that there exist$(1-\varepsilon,\ell, O(\ell/\varepsilon))$-list-recoverable RS codes with rate$\Omega\left(\frac{\varepsilon}{\sqrt{\ell}(\log(1/\varepsilon)+1)}\right)$. Along the way we use our techniques to give a new proof of a result of Blackburn on optimal linear perfect hash matrices, and strengthen it to obtain a construction of strongly perfect hash matrices. To derive the results in this paper we show a surprising connection of the above problems to graph theory, and in particular to the tree packing theorem of Nash-Williams and Tutte. We also state a new conjecture that generalizes the tree-packing theorem to hypergraphs, and show that if this conjecture holds, then there would exist RS codes that are optimally (non-asymptotically) list-decodable.11A full version of this paper is available online at https://arxiv.org/abs/2011.04453.

Let G be a connected graph on n vertices and C be an (n,k,d) code with d ≥ 2, defined on the alphabet {0,1} m . Suppose that for 1 ≤ i ≤ n, the i-th vertex of G holds an input symbol x i ∈{0,1}mand let x⃗ = (x1,...,xn) ∈{0,1}mnbe the input vector formed by those symbols. Assume that each vertex of G can communicate with its neighbors by transmitting messages along the edges, and these vertices must decide deterministically, according to a predetermined communication protocol, that whether x⃗ ∈ C. Then what is the minimum communication cost to solve this problem? Moreover, if x⃗ ∉ C, say, there is less than ⌊(d-1)/2⌋ input errors among the x i 's, then what is the minimum communication cost for error correction? We initiate the study of the two problems mentioned above. For the error detection problem, we obtain two lower bounds on the communication cost as functions of n,k,d,m, and our bounds are tight for several graphs and codes. For the error correction problem, we design a protocol which can efficiently correct a single input error when G is a cycle and C is a repetition code. We also present several interesting problems for further research. Full version is available at.

List-decoding of Reed-Solomon (RS) codes beyond the so called Johnson radius has been one of the main open questions in coding theory and theoretical computer science since the work of Guruswami and Sudan. It is now known by the work of Rudra and Wootters, using techniques from high dimensional probability, that over large enough alphabets there exist RS codes that are indeed list-decodable beyond this radius.

For fixed integers $r\ge 3,e\ge 3,v\ge r+1$, an $r$-uniform hypergraph is called $\mathscr{G}_r(v,e)$-free if the union of any $e$ distinct edges contains at least $v+1$ vertices. Brown, Erdös, and Sós showed that the maximum number of edges of such a hypergraph on $n$ vertices, denoted as $f_r(n,v,e)$, satisfies $\Omega(n^{\frac{er-v}{e-1}})=f_r(n,v,e)=O(n^{\lceil\frac{er-v}{e-1}\rceil})$. For sufficiently large $n$ and $e-1\mid er-v$, the lower bound matches the upper bound up to a constant factor, which depends only on $r,v,e$; whereas for $e-1\nmid er-v$, in general it is a notoriously hard problem to determine the correct exponent of $n$. Among other results, we improve the above lower bound by showing that $f_r(n,v,e)=\Omega(n^{\frac{er-v}{e-1}}(\log n)^{\frac{1}{e-1}})$ for any $r,e,v$ satisfying $\gcd(e-1,er-v)=1$. The hypergraph we constructed is in fact $\mathscr{G}_r(ir-\lceil\frac{(i-1)(er-v)}{e-1}\rceil,i)$-free for every $2\le i\le e$, and it has several interesting applications in coding theory. The proof of the new lower bound is based on a novel application of the lower bound on the hypergraph independence number due to Duke, Lefmann, and Rödl.

An $r$-uniform hypergraph is called $t$-cancellative if for any $t+2$ distinct edges $A_1,\ldots,A_t,B,C$, it holds that $(\cup_{i=1}^t A_i)\cup B\neq (\cup_{i=1}^t A_i)\cup C$. It is called $t$-union-free if for any two distinct subsets $\mathcal{A}, \mathcal{B}$, each consisting of at most $t$ edges, it holds that $\cup_{A\in \mathcal{A}} A\neq \cup_{B\in \mathcal{B}} B$. Let $C_t(n,r)$ (resp., $U_t(n,r)$) denote the maximum number of edges of a $t$-cancellative (resp., $t$-union-free) $r$-uniform hypergraph on $n$ vertices. Among other results, we show that for fixed $r\ge 3,t\ge 3$ and $n\rightarrow\infty$, $\Omega(n^{\lfloor\frac{2r}{t+2}\rfloor+\frac{2r\pmod{t+2}}{t+1}})=C_t(n,r)=O(n^{\lceil\frac{r}{\lfloor t/2\rfloor+1}\rceil})\text{ and } \Omega(n^{\frac{r}{t-1}})=U_t(n,r)=O(n^{\lceil\frac{r}{t-1}\rceil}),$ thereby significantly narrowing the gap between the previously known lower and upper bounds. In particular, we determine the Turán exponent of $C_t(n,r)$ when $2\mid t \text{ and } (t/2+1)\mid r$, and of $U_t(n,r)$ when $(t-1)\mid r$. The main tool used in proving the two lower bounds is a novel connection between these problems and sparse hypergraphs.

For fixed integers r ≥ 2, e ≥ 2, v ≥ r + 1, an r-uniform hypergraph is called Gr(v, e)-free if the union of any e distinct edges contains at least v+1 vertices. Let Gr(n, v, e) denote the maximum number of edges in a Gr(v, e)-free r-uniform hypergraph on n vertices. Brown, Erdós and Sós showed in 1973 that there exist constants c1, c2depending only on r, e, v such that c1ner-v/e-1≤ fr(n,v,e) ≤ c2n[er-v/e-1]For e - 1|er - v, the lower bound matches the upper bound up to a constant factor; whereas for e - 1 t er - v, it is a notoriously hard problem to determine the correct exponent of n. Our main result is an er-v improvement fr(n, v, e) = Ω(n e-1 (log n) 1 e-1 ) for any r, e, v satisfying gcd(e - 1, er - v) = 1. Moreover, the hypergraph we constructed is not only gr(v, e)-free but also universally Gr(ir - Γ (i-1)(-1er-v) 1 + i)-free for every 2 <; i <; e. Interestingly, e our new lower bound provides improved constructions for several seemingly unrelated topics in Coding Theory, namely, Parent-Identifying Set Systems, uniform Combinatorial Batch Codes and optimal Locally Recoverable Codes.

The centralized coded caching scheme is a technique proposed by Maddah-Ali and Niesen as a method to reduce the network burden in peak times in a wireless network system. Yanet al.reformulate the problem as designing a corresponding placement delivery array and propose two new schemes from this perspective. These schemes significantly reduce the rate compared with the uncoded caching schemes. However, to implement these schemes, each file should be cut into$F$pieces, where$F$grows exponentially with the number of users$K$. Such a constraint is obviously infeasible in the practical setting, especially when$K$is large. Thus, it is desirable to design caching schemes with constant rate$R$(independent of$K$) as well as smaller$F$. In this paper, we view the centralized coded caching problem in a hypergraph perspective and show that designing a feasible placement delivery array is equivalent to constructing a linear and (6,3)-free 3-uniform 3-partite hypergraph. Several new results and constructions arise from our novel point of view. First, by using the famous (6,3)-theorem in extremal graph theory, we show that constant rate placement delivery arrays with$F$growing linearly with$K$do not exist. Second, we present two infinite classes of placement delivery arrays to show that constant rate caching schemes with$F$growing sub-exponentially with$K$do exist.

Frameproof codes are used to fingerprint digital data. They can prevent copyrighted materials from unauthorized use. In this paper, we study upper and lower bounds for$w$-frameproof codes of length$N$over an alphabet of size$q$. The upper bound is based on a combinatorial approach and the lower bound is based on a probabilistic construction. Both bounds can improve one of the previous results when$q$is small compared with$w$, say$cq\leq w$for some constant$c\leq q$. Furthermore, we pay special attention to binary frameproof codes. We show a binary$w$-frameproof code of length$N$cannot have more than$N$codewords if$N<\binom {w+1}{2}$.

Separating hash families are useful combinatorial structures which are generalizations of many well-studied objects in combinatorics, cryptography, and coding theory. In this paper, using tools from graph theory and additive number theory, we solve several open problems and conjectures concerning bounds and constructions for separating hash families. Firstly, we discover that the cardinality of a separating hash family satisfies a Johnson-type inequality. As a result, we obtain a new upper bound, which is superior to all previous ones. Secondly, we present a construction for an infinite class of perfect hash families. It is based on the Hamming graphs in coding theory and generalizes many constructions that appeared before. It provides an affirmative answer to both Bazrafshan and Trung's open problem on separating hash families and Alon and Stav's conjecture on parent-identifying codes. Thirdly, let $p_t(N,q)$ denote the maximal cardinality of a $t$-perfect hash family of length $N$ over an alphabet of size $q$. Walker and Colbourn conjectured that $p_3(3,q)=o(q^2)$. We verify this conjecture by proving $q^{2-o(1)}

Given n items with at most d of which being positive, instead of testing these items individually, the theory of combinatorial group testing aims to identify all positive items using as few tests as possible. This paper is devoted to a fundamental and thirty-year-old problem in the nonadaptive group testing theory. A binary matrix is called d-disjunct if the Boolean sum of arbitrary d columns does not contain another column not in this collection. Let T(d) denote the minimal t, such that there exists a t × n d-disjunct matrix with n > t. T(d) can also be viewed as the minimal t such that there exists a nonadaptive group testing scheme, which is better than the trivial one that tests each item individually. It was known that T(d) ≥ (2d+2) and was conjectured that T(d) ≥ (d + 1)2. In this paper, we narrow the gap by proving T(d)/d2≥ (15 + √33)/24, a quantity in [6/7,7/8].

Multiply constant-weight codes (MCWCs) were introduced recently to improve the reliability of certain physically unclonable function response. In this paper, the bounds of MCWCs and the constructions of optimal MCWCs are studied. First, we derive three different types of upper bounds which improve the Johnson-type bounds given by Cheeet al.for some parameters. The asymptotic lower bound of MCWCs is also examined. Then, we obtain the asymptotic existence of two classes of optimal MCWCs, which shows that the Johnson-type bounds for MCWCs with distances$2\sum _{i=1}^{m}w_{i}-2$or$2mw-2w$are asymptotically exact. Finally, we construct a class of optimal MCWCs with total weight four and distance six by establishing the connection between such MCWCs and a new kind of combinatorial structures. As a consequence, the maximum sizes of MCWCs with total weight less than or equal to four are determined almost completely.