Computing Groebner Bases for Finding Codewords of Small Weight
Date: July 19th (Friday)
Time: 17:00-17:30
Abstract
We describe a relationship between codewords of small weight in codes and
algebraic systems of equations. These systems are constructed from the (generalized)
Newton's identities, and solving these systems is equivalent to find codewords of weight less
than a given weight. We propose to compute a Groebner basis of the system, by using the
Buchberger algorithm, or variants. These is a complexity barrier, which make the method
inefficient for long codes. However, for small length, valuable information is obtained on
codewords, because their Fourier transform is then known. Examples are given.
