We consider linear codes over a field in which the error values are restricted to a subgroup of its unit group. This scenario captures Lee distance codes as well as codes over the Gaussian or Eisenstein integers. Codes correcting restricted errors gained increased attention recently in the context of code-based cryptography. In this work we provide new constructions of codes over the Gaussian or Eisenstein integers correcting two or three errors. We adapt some techniques from Roth and Siegel's work on codes for the Lee metric. We propose two construction methods, which may be seen of geometric and algebraic flavor, respectively.

A visual cryptography scheme is a secret sharing scheme in which the secret information is an image and the shares are printed on transparencies, so that the secret image can be recovered by simply stacking the shares on top of each other. Such schemes do therefore not require any knowledge of cryptography tools to recover the secret, and they have widespread applications, for example, when sharing QR codes or medical images.In this work we deal with visual cryptography threshold schemes for color images. Our color model differs from most previous work by allowing arbitrary colors to be stacked, resulting in a possibly different color. This more general color monoid model enables us to achieve shorter pixel expansion and higher contrast than comparable schemes. We revisit the polynomial framework of Koga and Ishihara for constructing visual cryptography schemes and apply the monoid ring to obtain new schemes for color visual cryptography.

The analysis of the decoding failure rate of the bit-flipping algorithm has received increasing attention. For a binary linear code we consider the minimum number of rows in a parity-check matrix such that the bit-flipping algorithm is able to correct errors up to the minimum distance without any decoding failures. We initiate a study of this bit-flipping redundancy, which is akin to the stopping set, trapping set or pseudocodeword redundancy of binary linear codes, and focus in particular on codes based on finite geometries.

We present a list decoding algorithm for quaternary negacyclic codes over the Lee metric. To achieve this result, we use a Sudan-Guruswami type list decoding algorithm for Reed- Solomon codes over certain ring alphabets. Our decoding strategy for negacyclic codes over the ring ${\mathbb{Z}_4}$ combines the list decoding algorithm by Wu with the Gröbner basis approach for solving a key equation due to Byrne and Fitzpatrick.

This paper presents the first decoding algorithm for Gabidulin codes over Galois rings with provable quadratic complexity in the code length. The new method consists of two steps: (1) solving a syndrome-based key equation to obtain the annihilator polynomial of the error and therefore the column space of the error, (2) solving a key equation based on the received word in order to reconstruct the error vector. This two-step approach became necessary since standard solutions as the Euclidean algorithm do not properly work over rings.

By using the value assignment of Chen and Kløve we present new results on the pseudocodeword redundancy of binary linear codes. In particular, we give some upper bounds on the pseudoredundancies of certain codes with repeated coordinates and of certain shortened subcodes. We also investigate several kinds of k-dimensional binary codes and compute their exact pseudocodeword redundancy.

Revisiting an approach by Conway and Sloane we investigate a collection of optimal non-linear binary codes and represent them as (non-linear) codes over ℤ4. The Fourier transform will be used in order to analyze these codes, which leads to a new algebraic representation involving subgroups of the group of units in a certain ring. One of our results is a new representation of Best's (10, 40, 4) code as a coset of a subgroup in the group of invertible elements of the group ring ℤ4[ℤ5]. This yields a particularly simple algebraic decoding algorithm for this code. The technique at hand is further applied to analyze Julin's (12, 144, 4) code and the (12, 24, 12) Hadamard code. It can also be used in order to construct a (non-optimal) binary (14, 56, 6) code.

For a binary linear code, the pseudocodeword redundancy with respect to the additive white Gaussian noise channel, the binary symmetric channel, or the max-fractional weight is defined to be the smallest number of rows in a parity-check matrix such that the corresponding minimum pseudoweight is equal to the minimum Hamming distance of the code. It is shown that most codes do not have a finite pseudocodeword redundancy. Also, upper bounds on the pseudocodeword redundancy for some families of codes, including codes based on designs, are provided. The pseudocodeword redundancies for all codes of small length (at most 9) are computed. Furthermore, comprehensive results are provided on the cases of cyclic codes of length at most 250 for which the eigenvalue bound of Vontobel and Koetter is sharp.

We define the AWGNC, BSC, and max-fractional pseudocodeword redundancy p(C) of a code C as the smallest number of rows in a parity-check matrix such that the corresponding minimum pseudoweight is equal to the minimum Hamming distance of C. We show that most codes do not have a finite p(C). We also provide bounds on the pseudocodeword redundancy for some families of codes, including codes based on designs.

People have been studying the following problem: Given a finite set S with a hidden (black box) binary operation * : S times S rarr S which might come from a group law, and suppose you have access to an oracle that you can ask for the operation x*y of single pairs (x, y) isin S2you choose. What is the minimal number of queries to the oracle until the whole binary operation is recovered, i.e. you know x*y for all x,y isin S? This problem can trivially be solved by using |S|2queries to the oracle, so the question arises under which circumstances you can succeed with a significantly smaller number of queries. In this presentation we give a lower bound on the number of queries needed for general binary operations. On the other hand, we present algorithms solving this problem by using |S| queries, provided that * is an abelian group operation. We also investigate black box rings and give lower und upper bounds for the number of queries needed to solve product recovering in this case.