Source author record

Gennian Ge

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Information Theory math.IT math.CO Discrete Mathematics math.MG math.NT math.CA math.PR

Catalog footprint

Research overview

52works

8topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

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.

preprint2023arXiv

On lattice tilings of $\mathbb{Z}^{n}$ by limited magnitude error balls $\mathcal{B}(n,2,1,1)$

Limited magnitude error model has applications in flash memory. In this model, a perfect code is equivalent to a tiling of $\mathbb{Z}^n$ by limited magnitude error balls. In this paper, we give a complete classification of lattice tilings of $\mathbb{Z}^n$ by limited magnitude error balls $\mathcal{B}(n,2,1,1)$ .

preprint2022arXiv

A generic framework for coded caching and distributed computation schemes

Several network communication problems are highly related such as coded caching and distributed computation. The centralized coded caching focuses on reducing the network burden in peak times in a wireless network system and the coded distributed computation studies the tradeoff between computation and communication in distributed system. In this paper, motivated by the study of the only rainbow $3$ -term arithmetic progressions set, we propose a unified framework for constructing coded caching schemes. This framework builds bridges between coded caching schemes and lots of combinatorial objects due to the freedom of the choices of families and operations. We prove that any scheme based on a placement delivery array (PDA) can be represented by a rainbow scheme under this framework and lots of other known schemes can also be included in this framework. Moreover, we also present a new coded caching scheme with linear subpacketization and near constant rate using the only rainbow $3$ -term arithmetic progressions set. Next, we modify the framework to be applicable to the distributed computing problem. We present a new transmission scheme in the shuffle phase and show that in certain cases it could have a lower communication load than the schemes based on PDAs or resolvable designs with the same number of files.

preprint2022arXiv

Coding schemes for locally balanced constraints

Motivated by applications in DNA-based storage, we study explicit encoding and decoding schemes of binary strings satisfying locally balanced constraints, where the $(\ell,δ)$ -locally balanced constraint requires that the weight of any consecutive substring of length $\ell$ is between $\frac{\ell}{2}-δ$ and $\frac{\ell}{2}+δ$ . In this paper we present coding schemes for the strongly locally balanced constraints and the locally balanced constraints, respectively. Moreover, we introduce an additional result on the linear recurrence formula of the number of binary strings which are $(6,1)$ -locally balanced, as a further attempt to both capacity characterization and new coding strategies for locally balanced constraints.

preprint2022arXiv

Covering Grassmannian Codes: Bounds and Constructions

Grassmannian $\mathcal{G}_q(n,k)$ is the set of all $k$ -dimensional subspaces of the vector space $\mathbb{F}_q^n.$ Recently, Etzion and Zhang introduced a new notion called covering Grassmannian code which can be used in network coding solutions for generalized combination networks. An $α$ - $(n,k,δ)_q^c$ covering Grassmannian code $\mathcal{C}$ is a subset of $\mathcal{G}_q(n,k)$ such that every set of $α$ codewords of $\mathcal{C}$ spans a subspace of dimension at least $δ+k$ in $\mathbb{F}_q^n.$ In this paper, we derive new upper and lower bounds on the size of covering Grassmannian codes. These bounds improve and extend the parameter range of known bounds.

preprint2022arXiv

On the lower bound for kissing numbers of $\ell_p$ -spheres in high dimensions

In this paper, we give some new lower bounds for the kissing number of $\ell_p$ -spheres. These results improve the previous work due to Xu (2007). Our method is based on coding theory.

preprint2022arXiv

On the lower bound for packing densities of superballs in high dimensions

Define the superball with radius $r$ and center ${\boldsymbol 0}$ in $\mathbb{R}^n$ to be the set $\left\{{\boldsymbol x}\in\mathbb{R}^n:\sum_{j=1}^{m}\left(x_{k_j+1}^2+x_{k_j+2}^2+\cdots+x_{k_{j+1}}^2\right)^{p/2}\leq r^p\right\},0=k_1<k_2<\cdots<k_{m+1}=n,$ which is a generalization of $\ell_p$ -balls. We give two new proofs for the celebrated result that for $1<p\leq2$ , the translative packing density of superballs in $\mathbb{R}^n$ is $Ω(n/2^n)$ . This bound was first obtained by Schmidt, with subsequent constant factor improvement by Rogers and Schmidt, respectively. Our first proof is based on the hard superball model, and the second proof is based on the independence number of a graph. We also investigate the entropy of packings, which measures how plentiful such packings are.

preprint2021arXiv

Inverse problems of the Erdős-Ko-Rado type theorems for families of vector spaces and permutations

Ever since the famous Erdős-Ko-Rado theorem initiated the study of intersecting families of subsets, extremal problems regarding intersecting properties of families of various combinatorial objects have been extensively investigated. Among them, studies about families of subsets, vector spaces and permutations are of particular concerns. Recently, the authors proposed a new quantitative intersection problem for families of subsets: For $\mathcal{F}\subseteq {[n]\choose k}$ , define its \emph{total intersection number} as $\mathcal{I}(\mathcal{F})=\sum_{F_1,F_2\in \mathcal{F}}|F_1\cap F_2|$ . Then, what is the structure of $\mathcal{F}$ when it has the maximal total intersection number among all families in ${[n]\choose k}$ with the same family size? In \cite{KG2020}, the authors studied this problem and characterized extremal structures of families maximizing the total intersection number of given sizes. In this paper, we consider the analogues of this problem for families of vector spaces and permutations. For certain ranges of family size, we provide structural characterizations for both families of subspaces and families of permutations having maximal total intersection numbers. To some extent, these results determine the unique structure of the optimal family for some certain values of $|\mathcal{F}|$ and characterize the relation between having maximal total intersection number and being intersecting. Besides, we also show several upper bounds on the total intersection numbers for both families of subspaces and families of permutations of given sizes.

preprint2021arXiv

New bounds and constructions for constant weighted $X$ -codes

As a crucial technique for integrated circuits (IC) test response compaction, $X$ -compact employs a special kind of codes called $X$ -codes for reliable compressions of the test response in the presence of unknown logic values ( $X$ s). From a combinatorial view point, Fujiwara and Colbourn \cite{FC2010} introduced an equivalent definition of $X$ -codes and studied $X$ -codes of small weights that have good detectability and $X$ -tolerance. An $(m,n,d,x)$ $X$ -code is an $m\times n$ binary matrix with column vectors as its codewords. The parameters $d,x$ correspond to the test quality of the code. In this paper, bounds and constructions for constant weighted $X$ -codes are investigated. First, we obtain a general result on the maximum number of codewords $n$ for an $(m,n,d,x)$ $X$ -code of weight $w$ , and we further improve this lower bound for the case with $x=2$ and $w=3$ through the probabilistic method. Then, using tools from additive combinatorics and finite fields, we present some explicit constructions for constant weighted $X$ -codes with $d=3,7$ and $x=2$ , which are optimal for the case when $d=3, w=4$ and nearly optimal for the case when $d=3,w=3$ . We also consider a special class of $X$ -codes introduced in \cite{FC2010} and improve the best known lower bound on the maximum number of codewords for this kind of $X$ -codes.

preprint2021arXiv

On the minimal degree condition of graphs implying some properties of subgraphs

Erdős posed the problem of finding conditions on a graph $G$ that imply the largest number of edges in a triangle-free subgraph is equal to the largest number of edges in a bipartite subgraph. We generalize this problem to general cases. Let $δ_r$ be the least number so that any graph $G$ on $n$ vertices with minimum degree $δ_rn$ has the property $P_{r-1}(G)=K_rf(G),$ where $P_{r-1}(G)$ is the largest number of edges in an $(r-1)$ -partite subgraph and $K_rf(G)$ is the largest number of edges in a $K_r$ -free subgraph. We show that $\frac{3r-4}{3r-1}<δ_r\le\frac{4(3r-7)(r-1)+1}{4(r-2)(3r-4)}$ when $r\ge4.$ In particular, $δ_4\le 0.9415.$

preprint2021arXiv

Some Results on $k$ -Turán-good Graphs

For a graph $H$ and a $k$ -chromatic graph $F,$ if the Turán graph $T_{k-1}(n)$ has the maximum number of copies of $H$ among all $n$ -vertex $F$ -free graphs (for $n$ large enough), then $H$ is called $F$ -Turán-good, or $k$ -Turán-good for short if $F$ is $K_k.$ In this paper, we construct some new classes of $k$ -Turán-good graphs and prove that $P_4$ and $P_5$ are $k$ -Turán-good for $k\ge4.$

preprint2021arXiv

Some sum-product estimates in matrix rings over finite fields

We study some sum-product problems over matrix rings. Firstly, for $A, B, C\subseteq M_n(\mathbb{F}_q)$ , we have $|A+BC|\gtrsim q^{n^2},$ whenever $|A||B||C|\gtrsim q^{3n^2-\frac{n+1}{2}}$ . Secondly, if a set $A$ in $M_n(\mathbb{F}_q)$ satisfies $|A|\geq C(n)q^{n^2-1}$ for some sufficiently large $C(n)$ , then we have $\max\{|A+A|, |AA|\}\gtrsim \min\left\{\frac{|A|^2}{q^{n^2-\frac{n+1}{4}}}, q^{n^2/3}|A|^{2/3}\right\}.$ These improve the results due to The and Vinh (2020), and generalize the results due to Mohammadi, Pham, and Wang (2021). We also give a new proof for a recent result due to The and Vinh (2020). Our method is based on spectral graph theory and linear algebra.

preprint2020arXiv

Color isomorphic even cycles and a related Ramsey problem

In this paper, we first study a new extremal problem recently posed by Conlon and Tyomkyn~(arXiv: 2002.00921). Given a graph $H$ and an integer $k\geqslant 2$ , let $f_{k}(n,H)$ be the smallest number of colors $c$ such that there exists a proper edge-coloring of the complete graph $K_{n}$ with $c$ colors containing no $k$ vertex-disjoint color-isomorphic copies of $H$ . Using algebraic properties of polynomials over finite fields, we give an explicit proper edge-coloring of $K_{n}$ and show that $f_{k}(n, C_{4})=Θ(n)$ when $k\geqslant 3$ and $n\rightarrow\infty$ . The methods we used in the edge-coloring may be of some independent interest. We also consider a related generalized Ramsey problem. For given graphs $G$ and $H,$ let $r(G,H,q)$ be the minimum number of edge-colors (not necessarily proper) of $G$ , such that the edges of every copy of $H\subseteq G$ together receive at least $q$ distinct colors. Establishing the relation to the Turán number of specified bipartite graphs, we obtain some general lower bounds for $r(K_{n,n},K_{s,t},q)$ with a broad range of $q$ .

preprint2020arXiv

New lower bounds for the Turán density of $PG_{m}(q)$

Let $\mathcal{H}$ be an $r$ -uniform hypergraph. The Turán number $\text{ex}(n,\mathcal{H})$ is the maximum number of edges in an $n$ -vertex $\mathcal{H}$ -free $r$ -uniform hypergraph. The Turán density of $\mathcal{H}$ is defined by $π(\mathcal{H})=\lim_{n\rightarrow\infty}\frac{\text{ex}(n,\mathcal{H})}{\binom{n}{r}}.$ In this paper, we consider the Turán density of projective geometries. We give two new constructions of $PG_{m}(q)$ -free hypergraphs which improve some results given by Keevash (J. Combin. Theory Ser. A, 111: 289--309, 2005). Based on an upper bound of blocking sets of $PG_m(q)$ , we give a new general lower bound for the Turán density of $PG_{m}(q)$ . By a detailed analysis of the structures of complete arcs in $PG_2(q)$ , we also get better lower bounds for the Turán density of $PG_2(q)$ with $q=3,\ 4,\ 5,\ 7,\ 8$ .

preprint2020arXiv

On an inverse problem of the Erdős-Ko-Rado type theorems

A family of subsets $\mathcal{F}\subseteq {[n]\choose k}$ is called intersecting if any two of its members share a common element. Consider an intersecting family, a direct problem is to determine its maximal size and the inverse problem is to characterize its extremal structure and its corresponding stability. The famous Erdős-Ko-Rado theorem answered both direct and inverse problems and led the era of studying intersection problems for finite sets. In this paper, we consider the following quantitative intersection problem which can be viewed an inverse problem for Erdős-Ko-Rado type theorems: For $\mathcal{F}\subseteq {[n]\choose k}$ , define its \emph{total intersection} as $\mathcal{I}(\mathcal{F})=\sum_{F_1,F_2\in \mathcal{F}}|F_1\cap F_2|$ . Then, what is the structure of $\mathcal{F}$ when it has the maximal total intersection among all families in ${[n]\choose k}$ with the same family size? Using a pure combinatorial approach, we provide two structural characterizations of the optimal family of given size that maximizes the total intersection. As a consequence, for $n$ large enough and $\mathcal{F}$ of proper size, these characterizations show that the optimal family $\mathcal{F}$ is indeed $t$ -intersecting ( $t\geq 1$ ). To a certain extent, this reveals the relationship between properties of being intersecting and maximizing the total intersection. Also, we provide an upper bound on $\mathcal{I}(\mathcal{F})$ for several ranges of $|\mathcal{F}|$ and determine the unique optimal structure for families with sizes of certain values.

preprint2020arXiv

On color isomorphic subdivisions

Given a graph $H$ and an integer $k\geqslant 2$ , let $f_{k}(n,H)$ be the smallest number of colors $C$ such that there exists a proper edge-coloring of the complete graph $K_{n}$ with $C$ colors containing no $k$ vertex-disjoint color isomorphic copies of $H$ . In this paper, we prove that $f_{2}(n,H_{t})=Ω(n^{1+\frac{1}{2t-3}})$ where $H_{t}$ is the $1$ -subdivision of the complete graph $K_{t}$ . This answers a question of Conlon and Tyomkyn (arXiv: 2002.00921).

preprint2020arXiv

On the size of Nikodym sets in spaces over rings

A Nikodym set $\mathcal{N}\subseteq(\mathbb{Z}/(N\mathbb{Z}))^n$ is a set containing $L\setminus\{x\}$ for every $x\in(\mathbb{Z}/(N\mathbb{Z}))^n$ , where $L$ is a line passing through $x$ . We prove that if $N$ is square-free, then the size of every Nikodym set is at least $c_nN^{n-o(1)}$ , where $c_n$ only depends on $n$ . This result is an extension of the result in the finite field case.

preprint2020arXiv

On the Turán number of 1-subdivision of $K_{3,t}$

For a graph $H$ , the 1-subdivision of $H$ , denoted by $H'$ , is the graph obtained by replacing the edges of $H$ by internally disjoint paths of length 2. Recently, Conlon, Janzer and Lee (arXiv: 1903.10631) asked the following question: For any integer $s\ge2$ , estimate the smallest $t$ such that $\textup{ex}(n,K_{s,t}')=Ω(n^{\frac{3}{2}-\frac{1}{2s}})$ . In this paper, we consider the case $s=3$ . More precisely, we provide an explicit construction giving \begin{align*} \text{ex}(n,K_{3,30}')=Ω(n^{\frac{4}{3}}), \end{align*} which reduces the estimation for the smallest value of $t$ from a magnitude of $10^{56}$ to the number $30$ . The construction is algebraic, which is based on some equations over finite fields.

preprint2020arXiv

Some tight lower bounds for Turán problems via constructions of multi-hypergraphs

Recently, several hypergraph Turán problems were solved by the powerful random algebraic method. However, the random algebraic method usually requires some parameters to be very large, hence we are concerned about how these Turán numbers depend on such large parameters of the forbidden hypergraphs. In this paper, we determine the dependence on such specified large constant for several hypergraph Turán problems. More specifically, for complete $r$ -partite $r$ -uniform hypergraphs, we show that if $s_{r}$ is sufficiently larger than $s_{1},s_{2},\ldots,s_{r-1},$ then $\textup{ex}_{r}(n,K_{s_{1},s_{2},\ldots,s_{r}}^{(r)})=Θ(s_{r}^{\frac{1}{s_{1}s_{2}\cdots s_{r-1}}}n^{r-\frac{1}{s_{1}s_{2}\cdots s_{r-1}}}).$ For complete bipartite $r$ -uniform hypergraphs, we prove that if $s$ is sufficiently larger than $t,$ we have $\textup{ex}_{r}(n,K_{s,t}^{(r)})=Θ(s^{\frac{1}{t}}n^{r-\frac{1}{t}}).$ In particular, our results imply that the famous Kővári--Sós--Turán's upper bound $\textup{ex}(n,K_{s,t})=O(t^{\frac{1}{s}}n^{2-\frac{1}{s}})$ has the correct dependence on large $t$ . The main approach is to construct random multi-hypergraph via a variant of random algebraic method.

preprint2017arXiv

A strengthened inequality of Alon-Babai-Suzuki's conjecture on set systems with restricted intersections modulo p

Let $K=\{k_1,k_2,\ldots,k_r\}$ and $L=\{l_1,l_2,\ldots,l_s\}$ be disjoint subsets of $\{0,1,\ldots,p-1\}$ , where $p$ is a prime and $A=\{A_1,A_2,\ldots,A_m\}$ be a family of subsets of $[n]$ such that $|A_i|\pmod{p}\in K$ for all $A_i\in A$ and $|A_i\cap A_j|\pmod{p}\in L$ for $i\ne j$ . In 1991, Alon, Babai and Suzuki conjectured that if $n\geq s+\max_{1\leq i\leq r} k_i$ , then $|A|\leq {n\choose s}+{n\choose s-1}+\cdots+{n\choose s-r+1}$ . In 2000, Qian and Ray-Chaudhuri proved the conjecture under the condition $n\geq 2s-r$ . In 2015, Hwang and Kim verified the conjecture of Alon, Babai and Suzuki. In this paper, we will prove that if $n\geq 2s-2r+1$ or $n\geq s+\max_{1\leq i\leq r}k_i$ , then $|A|\leq{n-1\choose s}+{n-1\choose s-1}+\cdots+{n-1\choose s-2r+1}.$ This result strengthens the upper bound of Alon, Babai and Suzuki's conjecture when $n\geq 2s-2$ .

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

Constructions of Maximum Distance Separable Symbol-Pair Codes Using Cyclic and Constacyclic Codes

Symbol-pair code is a new coding framework which is proposed to correct errors in the symbol-pair read channel. In particular, maximum distance separable (MDS) symbol-pair codes are a kind of symbol-pair codes with the best possible error-correction capability. Employing cyclic and constacyclic codes, we construct three new classes of MDS symbol-pair codes with minimum pair-distance five or six. Moreover, we find a necessary and sufficient condition which ensures a class of cyclic codes to be MDS symbol-pair codes. This condition is related to certain property of a special kind of linear fractional transformations. A detailed analysis on these linear fractional transformations leads to an algorithm, which produces many MDS symbol-pair codes with minimum pair-distance seven.

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

Invertible binary matrix with maximum number of $2$ -by- $2$ invertible submatrices

The problem is related to all-or-nothing transforms (AONT) suggested by Rivest as a preprocessing for encrypting data with a block cipher. Since then there have been various applications of AONTs in cryptography and security. D'Arco, Esfahani and Stinson posed the problem on the constructions of binary matrices for which the desired properties of an AONT hold with the maximum probability. That is, for given integers $t\le s$ , what is the maximum number of $t$ -by- $t$ invertible submatrices in a binary matrix of order $s$ ? For the case $t=2$ , let $R_2(s)$ denote the maximal proportion of 2-by-2 invertible submatrices. D'Arco, Esfahani and Stinson conjectured that the limit is between 0.492 and 0.625. We completely solve the case $t=2$ by showing that $\lim_{s\rightarrow\infty}R_2(s)=0.5$ .

preprint2016arXiv

Maximum Distance Separable Codes for $b$ -Symbol Read Channels

Recently, Yaakobi et al. introduced codes for $b$ -symbol read channels, where the read operation is performed as a consecutive sequence of $b>2$ symbols. In this paper, we establish a Singleton-type bound on $b$ -symbol codes. Codes meeting the Singleton-type bound are called maximum distance separable (MDS) codes, and they are optimal in the sense they attain the maximal minimum $b$ -distance. Based on projective geometry and constacyclic codes, we construct new families of linear MDS $b$ -symbol codes over finite fields. And in some sense, we completely determine the existence of linear MDS $b$ -symbol codes over finite fields for certain parameters.

preprint2016arXiv

Narrow-Sense BCH Codes over $\gf(q)$ with Length $n=\frac{q^m-1}{q-1}$

Cyclic codes over finite fields are widely employed in communication systems, storage devices and consumer electronics, as they have efficient encoding and decoding algorithms. BCH codes, as a special subclass of cyclic codes, are in most cases among the best cyclic codes. A subclass of good BCH codes are the narrow-sense BCH codes over $\gf(q)$ with length $n=(q^m-1)/(q-1)$ . Little is known about this class of BCH codes when $q>2$ . The objective of this paper is to study some of the codes within this class. In particular, the dimension, the minimum distance, and the weight distribution of some ternary BCH codes with length $n=(3^m-1)/2$ are determined in this paper. A class of ternary BCH codes meeting the Griesmer bound is identified. An application of some of the BCH codes in secret sharing is also investigated.

preprint2016arXiv

New bounds of permutation codes under Hamming metric and Kendall's $τ$ -metric

Permutation codes are widely studied objects due to their numerous applications in various areas, such as power line communications, block ciphers, and the rank modulation scheme for flash memories. Several kinds of metrics are considered for permutation codes according to their specific applications. This paper concerns some improvements on the bounds of permutation codes under Hamming metric and Kendall's $τ$ -metric respectively, using mainly a graph coloring approach. Specifically, under Hamming metric, we improve the Gilbert-Varshamov bound asymptotically by a factor $n$ , when the minimum Hamming distance $d$ is fixed and the code length $n$ goes to infinity. Under Kendall's $τ$ -metric, we narrow the gap between the known lower bounds and upper bounds. Besides, we also obtain some sporadic results under Kendall's $τ$ -metric for small parameters.

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

On private information retrieval array codes

Given a database, the private information retrieval (PIR) protocol allows a user to make queries to several servers and retrieve a certain item of the database via the feedbacks, without revealing the privacy of the specific item to any single server. Classical models of PIR protocols require that each server stores a whole copy of the database. Recently new PIR models are proposed with coding techniques arising from distributed storage system. In these new models each server only stores a fraction $1/s$ of the whole database, where $s>1$ is a given rational number. PIR array codes are recently proposed by Fazeli, Vardy and Yaakobi to characterize the new models. Consider a PIR array code with $m$ servers and the $k$ -PIR property (which indicates that these $m$ servers may emulate any efficient $k$ -PIR protocol). The central problem is to design PIR array codes with optimal rate $k/m$ . Our contribution to this problem is three-fold. First, for the case $1<s\le 2$ , although PIR array codes with optimal rate have been constructed recently by Blackburn and Etzion, the number of servers in their construction is impractically large. We determine the minimum number of servers admitting the existence of a PIR array code with optimal rate for a certain range of parameters. Second, for the case $s>2$ , we derive a new upper bound on the rate of a PIR array code. Finally, for the case $s>2$ , we analyze a new construction by Blackburn and Etzion and show that its rate is better than all the other existing constructions.

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.

preprint2016arXiv

Some new results on permutation polynomials over finite fields

Permutation polynomials over finite fields constitute an active research area and have applications in many areas of science and engineering. In this paper, four classes of monomial complete permutation polynomials and one class of trinomial complete permutation polynomials are presented, one of which confirms a conjecture proposed by Wu et al. (Sci. China Math., to appear. Doi: 10.1007/s11425-014-4964-2). Furthermore, we give two classes of trinomial permutation polynomials, and make some progress on a conjecture about the differential uniformity of power permutation polynomials proposed by Blondeau et al. (Int. J. Inf. Coding Theory, 2010, 1, pp. 149-170).

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.

preprint2015arXiv

New constructions of quantum MDS convolutional codes derived from generalized Reed-Solomon codes

Quantum convolutional codes can be used to protect a sequence of qubits of arbitrary length against decoherence. In this paper, we give two new constructions of quantum MDS convolutional codes derived from generalized Reed-Solomon codes and obtain eighteen new classes of quantum MDS convolutional codes. Most of them are new in the sense that the parameters of the codes are different from all the previously known ones.

preprint2015arXiv

Quantum Block and Synchronizable Codes Derived from Certain Classes of Polynomials

One central theme in quantum error-correction is to construct quantum codes that have a large minimum distance. In this paper, we first present a construction of classical codes based on certain class of polynomials. Through these classical codes, we are able to obtain some new quantum codes. It turns out that some of quantum codes exhibited here have better parameters than the ones available in the literature. Meanwhile, we give a new class of quantum synchronizable codes with highest possible tolerance against misalignment from duadic codes.

preprint2015arXiv

Quantum Codes from Generalized Reed-Solomon Codes and Matrix-Product Codes

One of the central tasks in quantum error-correction is to construct quantum codes that have good parameters. In this paper, we construct three new classes of quantum MDS codes from classical Hermitian self-orthogonal generalized Reed-Solomon codes. We also present some classes of quantum codes from matrix-product codes. It turns out that many of our quantum codes are new in the sense that the parameters of quantum codes cannot be obtained from all previous constructions.

preprint2015arXiv

Snake-in-the-Box Codes for Rank Modulation under Kendall's $τ$ -Metric

For a Gray code in the scheme of rank modulation for flash memories, the codewords are permutations and two consecutive codewords are obtained using a push-to-the-top operation. We consider snake-in-the-box codes under Kendall's $τ$ -metric, which is a Gray code capable of detecting one Kendall's $τ$ -error. We answer two open problems posed by Horovitz and Etzion. Firstly, we prove the validity of a construction given by them, resulting in a snake of size $M_{2n+1}=\frac{(2n+1)!}{2}-2n+1$ . Secondly, we come up with a different construction aiming at a longer snake of size $M_{2n+1}=\frac{(2n+1)!}{2}-2n+3$ . The construction is applied successfully to $S_7$ .

preprint2015arXiv

Some Improvements on Locally Repairable Codes

The locally repairable codes (LRCs) were introduced to correct erasures efficiently in distributed storage systems. LRCs are extensively studied recently. In this paper, we first deal with the open case remained in \cite{q} and derive an improved upper bound for the minimum distances of LRCs. We also give an explicit construction for LRCs attaining this bound. Secondly, we consider the constructions of LRCs with any locality and availability which have high code rate and minimum distance as large as possible. We give a graphical model for LRCs. By using the deep results from graph theory, we construct a family of LRCs with any locality $r$ and availability $2$ with code rate $\frac{r-1}{r+1}$ and optimal minimum distance $O(\log n)$ where $n$ is the length of the code.

preprint2015arXiv

The Weight Hierarchy of Some Reducible Cyclic Codes

The generalized Hamming weights (GHWs) of linear codes are fundamental parameters, the knowledge of which is of great interest in many applications. However, to determine the GHWs of linear codes is difficult in general. In this paper, we study the GHWs for a family of reducible cyclic codes and obtain the complete weight hierarchy in several cases. This is achieved by extending the idea of \cite{YLFL} into higher dimension and by employing some interesting combinatorial arguments. It shall be noted that these cyclic codes may have arbitrary number of nonzeroes.

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

preprint2014arXiv

New pseudo-planar binomials in characteristic two and related schemes

Planar functions in odd characteristic were introduced by Dembowski and Ostrom in order to construct finite projective planes in 1968. They were also used in the constructions of DES-like iterated ciphers, error-correcting codes, and signal sets. Recently, a new notion of pseudo-planar functions in even characteristic was proposed by Zhou. These new pseudo-planar functions, as an analogue of planar functions in odd characteristic, also bring about finite projective planes. There are three known infinite families of pseudo-planar monomial functions constructed by Schmidt and Zhou, and Scherr and Zieve. In this paper, three new classes of pseudo-planar binomials are provided. Moreover, we find that each pseudo-planar function gives an association scheme which is defined on a Galois ring.

preprint2014arXiv

On the Existence of Certain Optimal Self-Dual Codes with Lengths Between $74$ and $116$

The existence of optimal binary self-dual codes is a long-standing research problem. In this paper, we present some results concerning the decomposition of binary self-dual codes with a dihedral automorphism group $D_{2p}$ , where $p$ is a prime. These results are applied to construct new self-dual codes with length $78$ or $116$ . We obtain $16$ inequivalent self-dual $[78,39,14]$ codes, four of which have new weight enumerators. We also show that there are at least $141$ inequivalent self-dual $[116,58,18]$ codes, most of which are new up to equivalence. Meanwhile, we give some restrictions on the weight enumerators of singly even self-dual codes. We use these restrictions to exclude some possible weight enumerators of self-dual codes with lengths $74$ , $76$ , $82$ , $98$ and $100$ .

preprint2014arXiv

On the Weight Distribution of Cyclic Codes with Niho Exponents

Recently, there has been intensive research on the weight distributions of cyclic codes. In this paper, we compute the weight distributions of three classes of cyclic codes with Niho exponents. More specifically, we obtain two classes of binary three-weight and four-weight cyclic codes and a class of nonbinary four-weight cyclic codes. The weight distributions follow from the determination of value distributions of certain exponential sums. Several examples are presented to show that some of our codes are optimal and some have the best known parameters.

preprint2013arXiv

Difference Sets with Few Character Values

The known families of difference sets can be subdivided into three classes: difference sets with Singer parameters, cyclotomic difference sets, and difference sets with gcd $(v,n)>1$ . It is remarkable that all the known difference sets with gcd $(v,n)>1$ have the so-called character divisibility property. In 1997, Jungnickel and Schmidt posed the problem of constructing difference sets with gcd $(v,n)>1$ that do not satisfy this property. In an attempt to attack this problem, we use difference sets with three nontrivial character values as candidates, and get some necessary conditions.

preprint2013arXiv

Some New Results on the Cross Correlation of $m$ -sequences

The determination of the cross correlation between an $m$ -sequence and its decimated sequence has been a long-standing research problem. Considering a ternary $m$ -sequence of period $3^{3r}-1$ , we determine the cross correlation distribution for decimations $d=3^{r}+2$ and $d=3^{2r}+2$ , where $\gcd(r,3)=1$ . Meanwhile, for a binary $m$ -sequence of period $2^{2lm}-1$ , we make an initial investigation for the decimation $d=\frac{2^{2lm}-1}{2^{m}+1}+2^{s}$ , where $l \ge 2$ is even and $0 \le s \le 2m-1$ . It is shown that the cross correlation takes at least four values. Furthermore, we confirm the validity of two famous conjectures due to Sarwate et al. and Helleseth in this case.

preprint2012arXiv

Association schemes related to Delsarte-Goethals codes

In this paper, we construct an infinite series of 9-class association schemes from a refinement of the partition of Delsarte-Goethals codes by their Lee weights. The explicit expressions of the dual schemes are determined through direct manipulations of complicated exponential sums. As a byproduct, the other three infinite families of association schemes are also obtained as fusion schemes and quotient schemes.

preprint2012arXiv

Constructions of Strongly Regular Cayley Graphs Using Index Four Gauss Sums

We give a construction of strongly regular Cayley graphs on finite fields $\F_q$ by using union of cyclotomic classes and index 4 Gauss sums. In particular, we obtain two infinite families of strongly regular graphs with new parameters.

preprint2012arXiv

Quaternary Constant-Composition Codes with Weight Four and Distances Five or Six

The sizes of optimal constant-composition codes of weight three have been determined by Chee, Ge and Ling with four cases in doubt. Group divisible codes played an important role in their constructions. In this paper, we study the problem of constructing optimal quaternary constant-composition codes with Hamming weight four and minimum distances five or six through group divisible codes and Room square approaches. The problem is solved leaving only five lengths undetermined. Previously, the results on the sizes of such quaternary constant-composition codes were scarce.

preprint2010arXiv

List Decodability at Small Radii

$A'(n,d,e)$ , the smallest $\ell$ for which every binary error-correcting code of length $n$ and minimum distance $d$ is decodable with a list of size $\ell$ up to radius $e$ , is determined for all $d\geq 2e-3$ . As a result, $A'(n,d,e)$ is determined for all $e\leq 4$ , except for 42 values of $n$ .

preprint2010arXiv

Spectrum of Sizes for Perfect Deletion-Correcting Codes

One peculiarity with deletion-correcting codes is that perfect $t$ -deletion-correcting codes of the same length over the same alphabet can have different numbers of codewords, because the balls of radius $t$ with respect to the Levenshte\uın distance may be of different sizes. There is interest, therefore, in determining all possible sizes of a perfect $t$ -deletion-correcting code, given the length $n$ and the alphabet size~ $q$ . In this paper, we determine completely the spectrum of possible sizes for perfect $q$ -ary 1-deletion-correcting codes of length three for all $q$ , and perfect $q$ -ary 2-deletion-correcting codes of length four for almost all $q$ , leaving only a small finite number of cases in doubt.

preprint2010arXiv

Supporting Information for the Paper: Optimal Ternary Constant-Composition Codes of Weight Four and Distance Five, IEEE Trans. Inform. Theory, To Appear

Supporting Information for the Paper: Optimal Ternary Constant-Composition Codes of Weight Four and Distance Five, IEEE Trans. Inform. Theory, To Appear.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Gennian Ge

Research overview

Is this your work?

52 publications

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

On lattice tilings of Zn\mathbb{Z}^{n}Zn by limited magnitude error balls B(n,2,1,1)\mathcal{B}(n,2,1,1)B(n,2,1,1)

A generic framework for coded caching and distributed computation schemes

Coding schemes for locally balanced constraints

Covering Grassmannian Codes: Bounds and Constructions

On the lower bound for kissing numbers of ℓp\ell_pℓp​-spheres in high dimensions

On the lower bound for packing densities of superballs in high dimensions

Inverse problems of the Erdős-Ko-Rado type theorems for families of vector spaces and permutations

New bounds and constructions for constant weighted XXX-codes

On the minimal degree condition of graphs implying some properties of subgraphs

Some Results on kkk-Turán-good Graphs

Some sum-product estimates in matrix rings over finite fields

Color isomorphic even cycles and a related Ramsey problem

New lower bounds for the Turán density of PGm(q)PG_{m}(q)PGm​(q)

On an inverse problem of the Erdős-Ko-Rado type theorems

On color isomorphic subdivisions

On the size of Nikodym sets in spaces over rings

On the Turán number of 1-subdivision of K3,tK_{3,t}K3,t​

Some tight lower bounds for Turán problems via constructions of multi-hypergraphs

A strengthened inequality of Alon-Babai-Suzuki's conjecture on set systems with restricted intersections modulo p

A New Piggybacking Design for Systematic MDS Storage Codes

Centralized coded caching schemes: A hypergraph theoretical approach

Constructions of Maximum Distance Separable Symbol-Pair Codes Using Cyclic and Constacyclic Codes

Good traceability codes do exist

Invertible binary matrix with maximum number of 222-by-222 invertible submatrices

Maximum Distance Separable Codes for bbb-Symbol Read Channels

Narrow-Sense BCH Codes over $\gf(q)$ with Length n=qm−1q−1n=\frac{q^m-1}{q-1}n=q−1qm−1​

New bounds of permutation codes under Hamming metric and Kendall's τττ-metric

New bounds on the number of tests for disjunct matrices

New results for traitor tracing schemes

On private information retrieval array codes

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

Some new results on permutation polynomials over finite fields

New bounds and constructions for multiply constant-weight codes

New constructions of quantum MDS convolutional codes derived from generalized Reed-Solomon codes

Quantum Block and Synchronizable Codes Derived from Certain Classes of Polynomials

Quantum Codes from Generalized Reed-Solomon Codes and Matrix-Product Codes

Snake-in-the-Box Codes for Rank Modulation under Kendall's τττ-Metric

Some Improvements on Locally Repairable Codes

The Weight Hierarchy of Some Reducible Cyclic Codes

New Bounds For Frameproof Codes

New pseudo-planar binomials in characteristic two and related schemes

On the Existence of Certain Optimal Self-Dual Codes with Lengths Between 747474 and 116116116

On the Weight Distribution of Cyclic Codes with Niho Exponents

Difference Sets with Few Character Values

Some New Results on the Cross Correlation of mmm-sequences

Association schemes related to Delsarte-Goethals codes

Constructions of Strongly Regular Cayley Graphs Using Index Four Gauss Sums

Quaternary Constant-Composition Codes with Weight Four and Distances Five or Six

List Decodability at Small Radii

Spectrum of Sizes for Perfect Deletion-Correcting Codes

Supporting Information for the Paper: Optimal Ternary Constant-Composition Codes of Weight Four and Distance Five, IEEE Trans. Inform. Theory, To Appear

See the researcher in context

Building this map preview

On lattice tilings of $\mathbb{Z}^{n}$ by limited magnitude error balls $\mathcal{B}(n,2,1,1)$

On the lower bound for kissing numbers of $\ell_p$ -spheres in high dimensions

New bounds and constructions for constant weighted $X$ -codes

Some Results on $k$ -Turán-good Graphs

New lower bounds for the Turán density of $PG_{m}(q)$

On the Turán number of 1-subdivision of $K_{3,t}$

Invertible binary matrix with maximum number of $2$ -by- $2$ invertible submatrices

Maximum Distance Separable Codes for $b$ -Symbol Read Channels

Narrow-Sense BCH Codes over $\gf(q)$ with Length $n=\frac{q^m-1}{q-1}$

New bounds of permutation codes under Hamming metric and Kendall's $τ$ -metric

Snake-in-the-Box Codes for Rank Modulation under Kendall's $τ$ -Metric

On the Existence of Certain Optimal Self-Dual Codes with Lengths Between $74$ and $116$

Some New Results on the Cross Correlation of $m$ -sequences