BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Gennian Ge

Gennian Ge appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
Information Theorymath.ITmath.CODiscrete Mathematicsmath.MGmath.NTmath.CAmath.PR

Catalog footprint

What is connected

52works
8topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

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.

Published work

52 published item(s)

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.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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.$

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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$.

0 citations0 reviewsNo code linkedOpen access
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$.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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).

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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$.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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$.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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].

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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).

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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$.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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}$.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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$.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access