ITAP stands for Information Theoretic Achievability Prover. So basically, it is intended for coming up with achievability proofs using a computer. As of now, it supports the following:
Achievability proofs of multi-source network coding using vector-linear codes: answer questions like 'Is this rate vector achievable using a vector linear code over the given finite field?'. If the answer is `yes` it also returns the vector linear code it found as a certificate of achievability. Otherwise, it just says 'no'.
Achievability proofs with multi-linear secret sharing schemes: answer questions 'Is there a multi-linear secret sharing scheme over GF(q) for this access structure?'
Representability test for integer polymatroids over a given finite field: answer questions like `Is the integer polymatroid associated with this rank vector linear over GF(q)?
Achievable Rate Region Computation: For a network coding instance, what is the rate region achievable using linear codes with maximum message size k and maximum code dimension d?
Above questions are very similar to each other, in that, we are looking for linear representations of integer polymatroids satisfying certain properties (i.e. network coding constraints, access structure or having a specified rank vecor respectively). In its most general form an achievability prover is a computer program that able to answer if there exists a joint distribution satisfying certain constraints on entropy function. It is not known how to design such a computer program, as it is closely related to the characterization of the entropy function. ITAP tries answering this existential question in a much restricted sense, i.e. with respect to the joint distributions arising from vector linear codes aka integer linear polymatroids. The main algorithm underlying ITAP is called Leiterspiel or the algorithm of snakes and ladders. See [BBFKKW06] for details. For answering the first question in the above list, one can also use the algebraic formulation of Koetter and Medard [KM03] or its refinements such as the path gain formulation of Subramanian and Thangaraj [ST10]. These formulations lead to a system of polynomial equations over a finite field and allows one to use Groebner basis computation algorithms to answer question 1. ITAP currently supports such computation using Singular [DGPS15] via the GAP interface to Singular[CG12].
generated by GAPDoc2HTML