Search

This thesis contains three topics, list decoding of rank-metric codes, local decoding of Reed-Muller codes and the design of tampering detection codes and its generalization non-malleable codes. The first two topics are the central problems in theoretical computer science and the last one has cryptographic background. They are all focused on the design or decoding of codes with certain properties. In the first topic, we present an explicit construction of rank-metric codes with constant ratio. Such codes are list decoded beyond unique decoding radius which answers an open problem in~\cite{Guru2015}. The ratio of our rank-metric codes can reach $1/2$. Our construction can be seen as a step toward the list decoding of square rank metric codes. These results appear in Chapter 2. In Chapter 3, we further develop a combinatorial tool contributed to this issue, namely subspace design set. Our result can be treated as a generalization of the construction in~\cite{Guru2013B}. In the second topic, we design an local decoding algorithm of Reed-Muller codes based on algebraic geometry codes. The traditional local decoding algorithm of Reed-Muller codes are based on the line decoding, i.e., the decoding of Reed-Solomon codes. If we want to recover multiple points, we have to run this line decoding multiple rounds. To overcome this drawback, we propose a curve decoding via algebraic geometry codes. Our local decoding algorithm can recover as many points as possible in one round. Moreover, our algorithm outperforms the previous local decoding algorithm in both the error probability and query length. %Based on this local decoding algorithm, we present a local list-decoder of Reed-Muller codes. Our local list-decoder runs in sub-linear time in code length and list decode Reed-Muller codes up to the radius $1-\sqrt{\frac{2d}{q}}$. Our result improves the best known local list-decoder over large field~\cite{STV2001}. %All these results can be found in Chapter 4. In our last topic, we focus on the design of tampering detection codes or non-malleable codes resistant to large families of tampering function. Our first result answers the open problem in~\cite{CPX15} by constructing asymptotic optimal systematic Algebraic Manipulation Detection codes. Our second result yields optimal-rate tampering detection codes resistant to the family of linearized polynomials with certain degree. Both of the results are included in Chapter 5. In Chapter 6, we design a class of linear-time encoding and decoding non-malleable codes which is resistant to the family of bit-wise tampering and permutation functions. Our codes extend the non-malleable codes in~\cite{CDD16} which are only resistant to the family of bit-wise tampering functions. ​Doctor of Philosophy (SPMS)

It is well known that a (divisible) design with a regular automorphism group (Singer group) is equivalent to a (relative) difference set in that group. Therefore, the results and tools in designs and difference sets sometimes can be transferred to each other. In this dissertation, we shall discuss three problems to illustrate how the two theories interplay with each other. The first problem is about the construction of relative difference sets. The fascinating point is that one can see through it how various algebraic tools can be applied to combinatorial problems. There are many results on the construction of relative difference sets, see [7],[10],[29],[30],[35],[37]. Unfortunately, most of the constructions work for abelian groups, but few for non-abelian ones, since algebraic tools in the latter case are limited. By investigating the elements in affine general linear groups, which are also automorphisms of some classical divisible designs, we obtain a new construction of infinite families of (p^{a},p^{b},p^{a},p^{a-b})-relative difference sets. This new construction shows that (p^{a},p^{b},p^{a},p^{a-b})-relative difference sets exist in many non-abelian groups which were not covered by previous constructions. DOCTOR OF PHILOSOPHY (SPMS)

Error-correcting codes have played an important role in improving efficiency and reliability in classical communication and data storage systems. This thesis is devoted to the design of error-correcting codes to combat the most crucial errors that arose from modern communication and data storage systems such as deletions, insertions, duplications (a special type of insertions), and we refer them as codes correcting edits. Designing codes correcting deletion and insertion errors has been the subject of a large body of works in the literature and to the best of our knowledge, there exist only constructions for optimal codes capable of correcting a single deletion or single insertion in permutation codes and q-ary codes. The research on codes combatting multiple errors is very limited. The main objective of this thesis is to design codes capable of correcting burst errors, i.e. those errors that occur at adjacent positions. Throughout this thesis, we propose several constructions of burst deletion/insertion-correcting codes over permutations, multipermutations or more generally, over a q-ary alphabet. Special attention is given to the case of burst deletion-correcting codes in permutations and multipermutations. Here, such codes improve the reliability and memory endurance of non-volatile memories such as flash memories. Besides code constructions, we also provide efficient error decoders to recover codewords from errors with linear-time complexity. In addition, we introduce codes correcting tandem duplications, a special type of insertion errors, that has applications that store data in living organisms. We are concerned with designing efficient channel encoders (or source decoders) that encode (decode) any arbitrary sequence (arbitrary codeword) to a corresponding codeword in our design codes (to the original sequence) with the purpose of achieving high rate and low complexity. Our encoding/decoding algorithms are based on enumerative coding, finite-state machine, and algebraic number theory. While these techniques are standard in constrained coding and combinatorics literature, our contribution is a detailed analysis of the space and time complexities of the respective algorithms. Doctor of Philosophy

The problem of determining extremal hypergraphs containing at most r isomorphic copies of some element of a given hypergraph family was first studied by Boros et al. in 2001. There are not many hypergraph families for which exact results are known concerning the size of the corresponding extremal hypergraphs, except for those equivalent to the classical Turan numbers. In this paper, we determine the size of extremal k-uniform hypergraphs containing at most one pair of 2-intersecting edges for k in {3,4}. We give a complete solution when k=3 and an almost complete solution (with eleven exceptions) when k=4., 17 pages, 5 figures

This paper introduces a new combinatorial construction for q-ary constant-weight codes which yields several families of optimal codes and asymptotically optimal codes. The construction reveals intimate connection between q-ary constant-weight codes and sets of pairwise disjoint combinatorial designs of various types., 12 pages

An n i? n matrix M is called a fooling-set matrix of size n if its diagonal entries are nonzero and M k , ? M ? , k = 0 for every k ? ? . Dietzfelbinger, Hromkovic, and Schnitger (1996) showed that n ? ( rk M ) 2 , regardless of over which field the rank is computed, and asked whether the exponent on rk M can be improved.We settle this question. In characteristic zero, we construct an infinite family of rational fooling-set matrices with size n = ( rk M + 1 2 ) . In nonzero characteristic, we construct an infinite family of matrices with n = ( 1 + o ( 1 ) ) ( rk M ) 2 .

We obtain a broadly applicable decomposition of group ring elements into a "subfield part" and a "kernel part". Applications include the verification of Lander's conjecture for all difference sets whose order is a power of a prime >3 and for all McFarland, Spence and Chen/Davis/Jedwab difference sets. We obtain a new general exponent bound for difference sets. We show that there is no circulant Hadamard matrix of order v with 4

This dissertation is devoted to the study of relative difference sets and circulant weighing matrices using algebraic tools. We are mainly interested in answering the existence problems for these objects: For what values of $v$ and $n$, does a circulant weighing matrix $CW(v,n)$ exist? For what values of $m$, $n$, $k$, $\lambda$ does a $(m, n, k, \lambda)$ difference set exist? The existence of such combinatorial structures is proved via explicit construction while non-existence proofs are based on algebraic and number theoretic methods and sometimes computer assistance. Circulant weighing matrices and relative difference sets exhibit some similarities. First of all, they can be characterized in terms of group ring equations. Hence, powerful algebraic methods can be adopted to extract information on the structure of these objects. Furthermore, their images under a character of a group satisfy the modulus equation $$X\bar{X}= n$$ where $X \in \Z[\zeta_v]$ and $n$ and $v$ are integers. In addition, these two combinatorial objects are closely related to each other as well as other well known combinatorial structures such as Hadamard designs, difference sets and sequences. Hence, methods used to study these combinatorial objects can be adapted to the study of the two combinatorial structures in question. Algebraic methods that are used in the study of these objects are the self-conjugacy approach, the multiplier approach, and the field descent method. We extend the usual concept of multipliers to group rings with cyclotomic integers as coefficients and develop new non-existence results. Seven open cases were solved using this approach. Solutions of the modulus equations are called Weil numbers. Knowledge of these Weil numbers helps to tackle the existence problems. We incorporate the field descent method in search for these Weil numbers and with the help of computer, we settle two other open cases. In total, we solved $18$ open cases of circulant weighing matrices of order less than $200$, as well as several infinite families of cases. Circulant weighing matrices are rare. In fact, all of our new results concerning circulant weighing matrices are non-existence results. Relative difference sets, on the other hand, have a higher chance for positive construction results. We employ binary as well as quaternary Golay sequences, Williamson matrices, and building sets to develop a recursive construction for $(2m, 2, 2m, m)$ relative difference sets. We introduce the term Golay transversal which serves as the ingredient for our construction. As a result, we obtain the most general known construction of normal $(2m, 2, 2m, m)$ relative difference sets, extending previously known results. We append the most updated version of Strassler's table concerning the existence status of circulant weighing matrices of order at most $200$ and weight at most $100$. Detailed references for each case are provided as well. For relative difference sets, a table of the existence status of Golay transversals in abelian groups were provided. ​Doctor of Philosophy (SPMS)

We show that under the self-conjugacy condition a McFarland difference set with p=2 and f≥ in an abelian group G can only exist,if the exponent of the Sylow 2-subgroups does not exceed 4.The method also works for odd p(where the exponent bound is p and is necessary and sufficient),so that we obtain a unified proof of the exponent bounds for MacFarland difference sets.We also correct a mistake in the proof of an exponent bound for (320,88,24)-difference sets in a previous paper. Accepted version

In this paper, we modify the standard definition of moments of ranks and cranks such that odd moments no longer trivially vanish. Denoting the new k-th rank (resp. crank) moments by N@?"k(n) (resp. M@?"k(n)), we prove the following inequality between the first rank and crank moments:M@?"1(n)>N@?"1(n). This inequality motivates us to study a new counting function, ospt(n), which is equal to M@?"1(n)-N@?"1(n). We also discuss higher order moments of ranks and cranks. Surprisingly, for every higher order moments of ranks and cranks, the following inequality holds:M@?"k(n)>N@?"k(n). This extends F.G. Garvan@?s result on the ordinary moments of ranks and cranks.

Group divisible designs (GDDs) play a crucial role in the development of combinatorial design theory. We know that GDDs require that each pair of points in distinct groups occurs in exactly $\lambda$ blocks. If this requirement is relaxed, i.e., each pair of points in distinct groups occurs in at most $\lambda$ blocks, we can obtain a new of class of designs called partial group divisible designs (PGDDs). In this thesis, we study the uniform PGDDs with block size three. In particular, we determine all possible sizes of uniform PGDDs with block size three and no repeated blocks, where each pair of points in distinct groups occurs either once or twice. The investigation into the sizes of PGDDs with the aforementioned properties are not only practical in design theory, but also applicable to some optimization problems in data replication schemes in computer science. ​Master of Science

The concept of group divisible codes, a generalization of group divisible designs with constant block size, is introduced in this paper. This new class of codes is shown to be useful in recursive constructions for constant-weight and constant-composition codes. Large classes of group divisible codes are constructed which enabled the determination of the sizes of optimal constant-composition codes of weight three (and specified distance), leaving only four cases undetermined. Previously, the sizes of constant-composition codes of weight three were known only for those of sufficiently large length., 13 pages, 1 figure, 4 tables

We show an interesting PBD-closure result for the set of lengths of constant-composition codes whose distance and size meet certain conditions. A consequence of this PBD-closure result is that the size of optimal constant-composition codes can be determined for infinite families of parameter sets from just a single example of an optimal code. As an application, the size of several infinite families of optimal constant-composition codes are derived. In particular, the problem of determining the size of optimal constant-composition codes having distance four and weight three is solved for all lengths sufficiently large. This problem was previously unresolved for odd lengths, except for lengths seven and eleven., 8 pages

Two Steiner triple systems $(X,{\cal A})$ and $(X,{\cal B})$ are said to intersect in $m$ pairwise disjoint blocks if $|{\cal A}\cap{\cal B}|=m$ and all blocks in ${\cal A}\cap{\cal B}$ are pairwise disjoint. For each $v$, we completely determine the possible values of $m$ such that there exist two Steiner triple systems of order $v$ intersecting in $m$ pairwise disjoint blocks.

We point out an interesting connection between Williamson matrices and relative difference sets in nonabelian groups. As a consequence, we are able to show that there are relative (4t,2,4t,2t)-difference sets in the dicyclic groups Q_{8t}=\la a,b|a^{4t}=b^4=1, a^{2t}=b^2, b^{-1}ab=a^{-1}\ra for all t of the form t=2^a\cdot 10^b \cdot 26^c \cdot m with a,b,c\ge 0, m\equiv 1\ (\mod 2), whenever 2m-1 or 4m-1 is a prime power or there is a Williamson matrix over \Z_m. This gives further support to an important conjecture of Ito IT5 which asserts that there are relative (4t,2,4t,2t)-difference sets in Q_{8t} for every positive integer t. We also give simpler alternative constructions for relative (4t,2,4t,2t) -difference sets in Q_{8t} for all t such that 2t-1 or 4t-1 is a prime power. Relative difference sets in Q_{8t} with these parameters had previously been obtained by Ito IT1. Finally, we verify Ito‘s conjecture for all t\le 46. Accepted version

The most powerful method for the study of finite geometries with regular or quasiregular automorphism groups G is to translate their definition into an equation over the integral group ring 2[G] and to investigate this equation by applying complex representations of G. For the definitions and the basic facts, see Section 2. If G is abelian, this approach boils down to proving or disproving the existence of elements of 2[G] with 0-1 coefficients whose character values are cyclotomic integers of certain prescribed absolute values. Up to now there have been two general methods to tackle this problem, namely, Hall's multiplier concept and Turyn's selfconjugacy approach. However, both methods need severe technical assumptions and thus are not applicable to many classes of problems. Despite many efforts over a period of more than 30 years no general method has been found to overcome these difficulties. In this paper, we present a new approach to the study of combinatorial structures via group ring equations which works without any restrictive assumptions. In order to understand the method of the present paper it will be instructive to briefly discuss the self-conjugacy concept first. Turyn [51] demonstrated that the character method for the study of group ring equations works very nicely under the so-called self-conjugacy condition. An integer n is called self-conjugate modulo m if all prime ideals above n in the mth cyclotomic field Q((m) are invariant under complex conjugation. Under this condition it is possible to find all cyclotomic integers in Q((m) of absolute value nt/2 for any positive integer t. It is the complete knowledge of the cyclotomic integers of prescribed absolute value which makes the character method work so well under the self-conjugacy condition. Since Turyn's fundamental work [51] there have been dozens of papers extending and refining his approach. However, all these results are restricted to the case of self-conjugacy, and that is a very severe restriction indeed. Namely, the "probability" that n is selfconjugate modulo m decreases exponentially fast in the number of distinct prime divisors of n and m; see Remark 2.2. This means that the self-conjugacy method fails in almost all cases. One may ask if it is possible to extend Turyn's method in order to get rid of the self-conjugacy assumption. It turns out that in general this is impossible at least with present day methods. The required complete knowledge of the cyclotomic integers of prescribed absolute value would yield an

This paper provides new exponent and rank conditions for the existence of abelian relative (p^a,p^b,p^a,p^a-b) -difference sets. It is also shown that no splitting relative (2^2c,2^d,2^2c,2^2c-d)-difference set exists if d > c and the forbidden subgroup is abelian. Furthermore, abelian relative (16, 4, 16, 4)-difference sets are studied in detail; in particular, it is shown that a relative (16, 4, 16, 4)-difference set in an abelian group G\not\cong Z_8\times Z_4\times Z_2 exists if and only if \exp(G)\le 4 or G= Z_8\times ( Z_2)^3 with N\cong Z_2\times Z_2. Accepted version

In this paper, a new family of relative difference sets with parameters (m,n,k,λ)=((q^7-1)/(q-1), 4(q-1), q^6, q^5/4) is constructed where q is a 2-power. The construction is based on the technique used in [2]. By a similar method, we also construct some new circulant weighing matrices of order q^(d-1) where q is a 2-power, d is odd and d => 5. Accepted version

Let p=7 mod 6 be a prime. Then there are integers a,b,c,d with a=15 mod 6, b= 0 mod 4, p^2=a^2+2(b^2+c^2+d^2), and 2ab=c^2-2cd-d^2. We show that there is a regular Hadamard matrix of order 4p2 provided that p=a±2b or p=a+δ12b+4δ2c+4δ1δ2d with δi=±1. Accepted version