Degree of comprehensiveness in Decoder docstrings

[David Lucas]

For now, the Decoder docstring only indicates something like that :

Construct a decoder for GRS codes. This decoder will use the <algorithm name> decoding algorithm.

Do you think I should add a small description?

For instance, for Gao algorithm, mention the Euclidean algorithm?

[Daniel Augot]

I think no. We should check what is sage prefered method to external references.

My opinon is that we could (should!) add "See Roth, Introduction to Coding Theory, 33rd edition, page 4788928'. A PhD thesis is perfectly acceptable, also.

Ok, I am an old timer, may be we could reference to some online resource, but they are rather bad for coding theory.

An intermediate solution would be arxiv references, and open access references.

Yet, it could be acceptable to say something about the internals of the algorithm when there is a problem.

Imagine that a very fast method from computer algebra could be very well used for a particular decoder, but is not yet available in sage.

Then we could say that we use a naive, home-made, algorithm for a particular subtask, waiting for sage to be more complete.

[Johan Rosenkilde]

There should definitely be more details than "Gao's algorithm". That's not necessarily understood by everyone (case in point, "Gao's algorithm" is not a widely known term, such as Guruswami-Sudan, for instance). Secondly, Sage usually gives some amount of mathematical description.

My opinion is that there should be a proper reference. "proper" means the same as in a publication, i.e. book, survey or original paper. Journal takes precedence over conference, which precedes unpublished (incl. open access). Use the citation syntax of docstrings.

Secondly, there should be enough description about the workings of the algorithm that someone fairly knowledgeable about it can figure out roughly how it works, and in particular, if it is the algorithm he is looking for. There doesn't need to be too many technicalities and implementation details (like in Gao, that we're using matrix-representation for the "Euclidean algorithm"). I would like it if the asymptotic complexity was stated, but I'm also a nerd in that respect.

For something advanced, like Guruswami-Sudan, it should be mentioned that there are several choices of Q-constructing algorithms and several root-finders, and the decoder will attempt to determine the fastest one to use, but that one can get fine-grained control by doing so-and-so.