BZPEER

preprint2023arXiv

Improved Gilbert-Varshamov bounds for hopping cyclic codes and optical orthogonal codes

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. Constant weight binary hopping cyclic codes are also known as optical orthogonal codes (OOCs). HCCs and OOCs have various practical applications and have been studied extensively over the years. The main concern of this paper is to present improved Gilbert-Varshamov type lower bounds for these 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 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 by a quadratic factor of the code length. As by-products, we also provide improved lower bounds for frequency hopping sequences sets and error-correcting weakly mutually uncorrelated codes. 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.

preprint2020arXiv

Degenerate Turán densities of sparse hypergraphs

For fixed integers $r>k\ge 2,e\ge 3$ , let $f_r(n,er-(e-1)k,e)$ be the maximum number of edges in an $r$ -uniform hypergraph in which the union of any $e$ distinct edges contains at least $er-(e-1)k+1$ vertices. A classical result of Brown, Erdős and Sós in 1973 showed that $f_r(n,er-(e-1)k,e)=Θ(n^k).$ The degenerate Turán density is defined to be the limit (if it exists) $π(r,k,e):=\lim_{n\rightarrow\infty}\frac{f_r(n,er-(e-1)k,e)}{n^k}.$ Extending a recent result of Glock for the special case of $r=3,k=2,e=3$ , we show that $π(r,2,3):=\lim_{n\rightarrow\infty}\frac{f_r(n,3r-4,3)}{n^2}=\frac{1}{r^2-r-1}$ for arbitrary fixed $r\ge 4$ . For the more general cases $r>k\ge 3$ , we show that $\frac{1}{r^k-r}\le\liminf_{n\rightarrow\infty}\frac{f_r(n,3r-2k,3)}{n^k}\le\limsup_{n\rightarrow\infty}\frac{f_r(n,3r-2k,3)}{n^k}\le \frac{1}{k!\binom{r}{k}-\frac{k!}{2}}.$ The main difficulties in proving these results are the constructions establishing the lower bounds. The first construction is recursive and purely combinatorial, and is based on a (carefully designed) approximate induced decomposition of the complete graph, whereas the second construction is algebraic, and is proved by a newly defined matrix property which we call {\it strongly 3-perfect hashing}.

preprint2020arXiv

Error Detection and Correction in Communication Networks

Let $G$ be a connected graph on $n$ vertices and $C$ be an $(n,k,d)$ code with $d\ge 2$ , defined on the alphabet set $\{0,1\}^m$ . Suppose that for $1\le i\le n$ , the $i$ -th vertex of $G$ holds an input symbol $x_i\in\{0,1\}^m$ and let $\vec{x}=(x_1,\ldots,x_n)\in\{0,1\}^{mn}$ be 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 $\vec{x}\in C$ . Then what is the minimum communication cost to solve this problem? Moreover, if $\vec{x}\not\in C$ , say, there is less than $\lfloor(d-1)/2\rfloor$ input errors among the $x_i$ 's, then what is the minimum communication cost for error correction? In this paper 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.

preprint2020arXiv

New Turán exponents for two extremal hypergraph problems

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$ $Ω(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 } Ω(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.

preprint2020arXiv

Sparse Hypergraphs with Applications to Coding Theory

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 $Ω(n^{\frac{er-v}{e-1}})=f_r(n,v,e)=\mathcal{O}(n^{\lceil\frac{er-v}{e-1}\rceil}).$ For $e-1\mid er-v$ , the lower bound matches the upper bound up to a constant factor; 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)=Ω(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.

preprint2020arXiv

The hat guessing number of graphs

Consider the following hat guessing game: $n$ players are placed on $n$ vertices of a graph, each wearing a hat whose color is arbitrarily chosen from a set of $q$ possible colors. Each player can see the hat colors of his neighbors, but not his own hat color. All of the players are asked to guess their own hat colors simultaneously, according to a predetermined guessing strategy and the hat colors they see, where no communication between them is allowed. Given a graph $G$ , its hat guessing number ${\rm{HG}}(G)$ is the largest integer $q$ such that there exists a guessing strategy guaranteeing at least one correct guess for any hat assignment of $q$ possible colors. In 2008, Butler et al. asked whether the hat guessing number of the complete bipartite graph $K_{n,n}$ is at least some fixed positive (fractional) power of $n$ . We answer this question affirmatively, showing that for sufficiently large $n$ , the complete $r$ -partite graph $K_{n,\ldots,n}$ satisfies ${\rm{HG}}(K_{n,\ldots,n})=Ω(n^{\frac{r-1}{r}-o(1)})$ . Our guessing strategy is based on a probabilistic construction and other combinatorial ideas, and can be extended to show that ${\rm{HG}}(\vec{C}_{n,\ldots,n})=Ω(n^{\frac{1}{r}-o(1)})$ , where $\vec{C}_{n,\ldots,n}$ is the blow-up of a directed $r$ -cycle, and where for directed graphs each player sees only the hat colors of his outneighbors.

preprint2016arXiv

A New Piggybacking Design for Systematic MDS Storage Codes

Distributed storage codes have important applications in the design of modern storage systems. In a distributed storage system, every storage node has a probability to fail and once an individual storage node fails, it must be reconstructed using data stored in the surviving nodes. Computation load and network bandwidth are two important issues we need to concern when repairing a failed node. The traditional maximal distance separable (MDS) storage codes have low repair complexity but high repair bandwidth. On the contrary, minimal storage regenerating (MSR) codes have low repair bandwidth but high repair complexity. Fortunately, the newly introduced piggyback codes combine the advantages of both ones. In this paper, by introducing a novel piggybacking design framework for systematic MDS codes, we construct a storage code whose average repair bandwidth rate, i.e., the ratio of average repair bandwidth and the amount of the original data, can be as low as $\frac{\sqrt{2r-1}}{r}$ , which significantly improves the ratio $\frac{r-1}{2r-1}$ of the previous result. In the meanwhile, every failed systematic node of the new code can be reconstructed quickly using the decoding algorithm of an MDS code, only with some additional additions over the underlying finite field. This is very fast compared with the complex matrix multiplications needed in the repair of a failed node of an MSR code.

preprint2016arXiv

Centralized coded caching schemes: A hypergraph theoretical approach

The centralized coded caching scheme is a technique proposed by Maddah-Ali and Niesen as a solution to reduce the network burden in peak times in a wireless system. Later Yan et al. reformulated the problem as designing a corresponding placement delivery array, and proposed two new schemes from this perspective. These schemes above significantly reduce the transmission rate $R$ , compared with the uncoded caching scheme. However, to implement the new schemes, each file should be cut into $F$ pieces, where $F$ increases exponentially with the number of users $K$ . Such 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 small $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 combinatorics, we show that constant rate caching schemes with $F$ growing linearly with $K$ do not exist. Second, we present two infinite classes of centralized coded caching schemes, which include the schemes of Ali-Niesen and Yan et al. as special cases, respectively. Moreover, our constructions show that constant rate caching schemes with $F$ growing sub-exponentially with $K$ do exist.

preprint2016arXiv

Good traceability codes do exist

Traceability codes are combinatorial objects introduced by Chor, Fiat and Naor in 1994 to be used to trace the origin of digital content in traitor tracing schemes. Let $F$ be an alphabet set of size $q$ and $n$ be a positive integer. A $t$ -traceability code is a code $\mathscr{C}\subseteq F^n$ which can be used to catch at least one colluder from a collusion of at most $t$ traitors. It has been shown that $t$ -traceability codes do not exist for $q\le t$ . When $q>t^2$ , $t$ -traceability codes with positive code rate can be constructed from error correcting codes with large minimum distance. Therefore, Barg and Kabatiansky asked in 2004 that whether there exist $t$ -traceability codes with positive code rate for $t+1\le q\le t^2$ . In 2010, Blackburn, Etzion and Ng gave an affirmative answer to this question for $q\ge t^2-\lceil t/2\rceil+1$ , using the probabilistic methods. However, they did not see how their probabilistic methods can be used to answer this question for the remaining values of $q$ . They even suspected that there may be a `Plotkin bound' of traceability codes that forbids the existence of such codes. In this paper, we give a complete answer to Barg-Kabatiansky's question (in the affirmative). Surprisingly, our construction is deterministic.

preprint2016arXiv

New bounds on the number of tests for disjunct matrices

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\times 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)\ge\binom{d+2}{2}$ and was conjectured that $T(d)\ge(d+1)^2$ . In this paper we narrow the gap by proving $T(d)/d^2\ge(15+\sqrt{33})/24$ , a quantity in [6/7,7/8].

preprint2016arXiv

New results for traitor tracing schemes

In the last two decades, several classes of codes are introduced to protect the copyrighted digital data. They have important applications in the scenarios like digital fingerprinting and broadcast encryption schemes. In this paper we will discuss three important classes of such codes, namely, frameproof codes, parent-identifying codes and traceability codes. Firstly, suppose $N(t)$ is the minimal integer such that there exists a binary $t$ -frameproof code of length $N$ with cardinality larger than $N$ , we prove that $N(t)\ge\frac{15+\sqrt{33}}{24} (t-2)^2$ , which is a great improvement of the previously known bound $N(t)\ge\binom{t+1}{2}$ . Moreover, we find that the determination of $N(t)$ is closely related to a conjecture of Erdős, Frankl and Füredi posed in the 1980's, which implies the conjectured value $N(t)=t^2+o(t^2)$ . Secondly, we derive a new upper bound for parent-identifying codes, which is superior than all previously known bounds. Thirdly, we present an upper bound for 3-traceability codes, which shows that a $q$ -ary 3-traceability code of length $N$ can have at most $cq^{\lceil N/9\rceil}$ codewords, where $c$ is a constant only related to the code length $N$ . It is the first meaningful upper bound for 3-traceability codes and our result supports a conjecture of Blackburn et al. posed in 2010.

preprint2016arXiv

Separating hash families: A Johnson-type bound and new constructions

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-Trung's open problem on separating hash families and Alon-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 II and Colbourn conjectured that $p_3(3,q)=o(q^2)$ . We verify this conjecture by proving $q^{2-o(1)}<p_3(3,q)=o(q^2)$ . Our proof can be viewed as an application of Ruzsa-Szemer{é}di's (6,3)-theorem. We also prove $q^{2-o(1)}<p_4(4,q)=o(q^2)$ . Two new notions in graph theory and additive number theory, namely rainbow cycles and $R$ -sum-free sets, are introduced to prove this result. These two bounds support a question of Blackburn, Etzion, Stinson and Zaverucha. Finally, we establish a bridge between perfect hash families and hypergraph Tur{á}n problems. This connection has not been noticed before. As a consequence, many new results and problems arise.

preprint2015arXiv

New bounds and constructions for multiply constant-weight codes

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. Firstly, we derive three different types of upper bounds which improve the Johnson-type bounds given by Chee {\sl et al.} in 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}^mw_i-2$ or $2mw-w$ 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.

preprint2014arXiv

New Bounds For Frameproof Codes

Frameproof codes are used to fingerprint digital data. It 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 previous results when $q$ is small compared to $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$ can not have more than $N$ codewords if $N<\binom{w+1}{2}$ .

Chong Shangguan

Research overview

Is this your work?

14 publications

Improved Gilbert-Varshamov bounds for hopping cyclic codes and optical orthogonal codes

Degenerate Turán densities of sparse hypergraphs

Error Detection and Correction in Communication Networks

New Turán exponents for two extremal hypergraph problems

Sparse Hypergraphs with Applications to Coding Theory

The hat guessing number of graphs

A New Piggybacking Design for Systematic MDS Storage Codes

Centralized coded caching schemes: A hypergraph theoretical approach

Good traceability codes do exist

New bounds on the number of tests for disjunct matrices

New results for traitor tracing schemes

Separating hash families: A Johnson-type bound and new constructions

New bounds and constructions for multiply constant-weight codes

New Bounds For Frameproof Codes

See the researcher in context

Building this map preview