Coding for Storage
Digital Sequences in Coding and Communication
Combinatorial Designs and their Applications
Topics of research
Here is a list of topics in which I was involved. In each one I will give one research problem I want to see solved, but seems to be extremely difficult to solve (a new topic will appear every few weeks from old ones to new ones). But, there are always some related questions which are easier to solve.
1. de Bruijn Sequences
A binary de Bruijn sequence of order n is a cyclic sequence in which, each window of size n appears exactly once in one priod of the sequence. The linear complexity of a sequence is the degree of the linear shift register with the least degree which generates the sequence. The lower and upper bounds on the linear complexity of binary de Bruijn sequences are well known. There are no sequences with linear complexity one above the lower bound. Are there de Bruijn sequences for all the other possible linear complexity values between the lower and upper bound?
2. Costas arrays
A Costas array of order n is an nxn permutation matrix of “blank”s and “dot”s (n “dot”s) such that all the lines connecting two distinct “dot”s are different either by direction of by magnitude. Does there exists a Costas for all orders? The conjecture is NO. The first order for which no Costas array is known is 32.
3. Steiner Systems
A Steiner system S(t,k,n) is a collection of k-subsets (called blocks) of an n-set, such that each t-subset of the n-set is contained in exactly one block. A set of n-t pairwise disjoint steiner systems S(t,t+1,n) is called a large set. Are there such sets for t=3 ? I conjecture that there are such sets and the problem is to construct them.
4. Perfect Codes
In his seminal work from 1973 which started the combination between coding theory and association schemes, Phillipe Delsarte asked whether there exist nontrivial perfect codes in the Johnson scheme. The conjecture is NO. This question was not answered yet and this is arguably the most intriguing question on perfect codes.
5. Gray Codes
A Gray code of order n and length k is a list of k distinct binary words of length n such that each two consecutive ones (including the first and the last) differ in exactly one position. A single track Gray code has the additional property that the consecutive elements of each coordinate of the codewords form the same cyclic sequence of length k. Does there exists a Gray code of order p, where p is a prime number, which contains all the binary words of length p, except for two. The conjecture is that the answer is YES.
6. Grassmannian Codes
A code in the Grassmannian consists of k-dimensional subspaces from an n-dimensional space over a finite field GF(q). The research was motivated lately due to an application in error-correcting codes for random network coding. One of the most intriguing question is the existence of q-analog of Steiner systems. We present here the first parameter to which the answer is unknown. Is there a set of 381 3-dimensional subspaces of a binary 7-space, such that each 2-dimensional subspace of the binary 7-space is contained in exactly one of these 381 subspaces? Such a structure is called the binary q-Fano plane.
7. Vector Network Codes
Recently, we have proved that vector network codes outperforms scalar network codes (with respect to the alphabet size) in multicast networks if the number of messages is at least three. For two messages we conjecture that both vector network codes and saclar network codes are equivalent. We would like to see a proof for this conjecture, or to present a network with two messages in which vector network coding outperforms scalar network coding with respect to the alphabet size.
8. Alphabet Size for Solvable Multicast Networks
What alphabet’s size is sufficient for a network coding solution for a multicast network with h messages and N receivers? If h=2 then the problem is solved. If h>2 then the known alphabet’s size is the smallest prime power greater than N-1. But, there is no known multicast network for which such a size is necessary. Finding such a network or improving this upper bound is a major open problem over a decade. Is the problem for h=3 is easier then the problem for h>3?