List of possible improvements to sage/coding

[P Purkayastha]

I had a list of improvements that could be potentially implemented. I will just dump that list here.

* consistent usage of parameters in upper bounds - see #16393

* more decoders in sage; see #13252
- bounded distance decoders
- Reed Solomon decoder is in #15764
- list decoding algorithms (also see above)
- decoders implemented in GSOC 2013 -- needs review; see #14973

* product codes

* concatenated codes

* non-binary Reed Muller codes (and implement binary Reed Muller in Sage directly?)

* generalized Reed Solomon codes

* AG codes and Goppa codes

* Permutation codes
- decoding permutation codes which are groups (see thesis of Bailey for
GAP programs)

* codes over rings -- see #6452

* Should be make each code into a class that inherits LinearCode, so that
custom decoders can be implemented? For instance, each code can have its
own Code.decode() method which implements the custom decoder.

- basu.

[David Joyner]

On Thu, Jul 10, 2014 at 6:33 AM, P Purkayastha <ppu...@gmail.com> wrote:
> This should be the thesis:
>
> www.math.carleton.ca/~robertb/thesis.pdf
>
> Title: Permutation Groups, Error-Correcting Codes and Uncoverings
> - Robert F Bailey
>

Thanks!

Forgot to cc the group:-)


> On Jul 10, 2014 6:26 PM, "David Joyner" <wdjo...@gmail.com> wrote:

>> Much appreciated, thank you!
>>
>> Do you have an online reference for the thesis of Bailey?
>>
>> > --
>> > You received this message because you are subscribed to the Google
>> > Groups "sage-coding-theory" group.
>> > To unsubscribe from this group and stop receiving emails from it, send
>> > an email to sage-coding-the...@googlegroups.com.
>> > To post to this group, send email to
>> > sage-codi...@googlegroups.com.
>> > To view this discussion on the web visit
>> > https://groups.google.com/d/msgid/sage-coding-theory/f83077e0-1b64-4947-9ee0-f3dfa0be7587%40googlegroups.com.
>> > For more options, visit https://groups.google.com/d/optout.

[Augot Daniel]

Thank you Basu for this list, which makes much sense.

In my institution (INRIA), I secured funding for hiring a software engineer (David Lucas) for a two year project, starting October 1st. The main thrust is to provide relevant and  reasonably fast algorithms for Reed-Solomon codes (Unique decoding, list decoding, "power decoding" and so on), polish code, etc. Then, other codes can be considered, as the project goes on.

Indeed, to my knowledge, concerning Guruswami-Sudan, there only exists low level Quintin's decoding library (that you mention), and percy++, which does not well export its decoding algorithm. I have also  in mind most of Johan Nielsen's code http://jsrn.dk/ and also recent algorithmic progress http://arxiv.org/abs/1402.0643.

The point is to be not ridiculously slow.  Many PhD students struggled for improving  GS algorithm, and many of their code has been lost. Now, with Quintin and Nielsen's publicly available (C and sage) code, and sage framework, may be it is time to  finally deliver something.

Also, a wider objective of this project is to discus with the community,  for improving for the sage coding library, APIwise. I have mainly in mind  application for computer science and cryptography, and this may change how things are viewed.

Best,

Daniel

[David Joyner]

On Thu, Jul 31, 2014 at 2:45 PM, Thomas Feulner
<thomas....@uni-bayreuth.de> wrote:
> Dear David,
>
> it would be great, if someone could assist me. I am not working in academics
> anymore and it is quite hard to find enough time for doing math in the

I didn't know that. I told people you were still in academics:-(

> evening. I already wrote a post on the list.
>

Thanks for that post.

> Personally, I think that it is very dangerous for Sage to put everything
> into its standard libraries. I think it would be much better to have a
> modular concept.
> Therefore, I would prefer to maintain my algorithm for canonical forms for
> ring-linear codes in one single package. The ticket 13398 already shows,
> that not too many mathematician seem to be interested in chain rings. We
> have to ask ourselves, respectively the community: is the standard the right
> place for codes over chain rings...?
>

Should this patch be changed to a python package which can be installed, then
posted somewhere other than on the trac?

Note that http://www.computeralgebra.uni-bayreuth.de/de/team/Feulner_Thomas/
returns a 404 error, as does
http://www.computeralgebra.uni-bayreuth.de/de/team/Feulner_Thomas/codecan-1_1_spkg.zip

> I hope, that this new list is the right place for such discussions.
>

Yes, and sorry for the late reply. (Busy semester:-)

> Best wishes,
> Thomas
>
>

>

[Dima Pasechnik]

On Wed, Sep 10, 2014 at 04:54:05PM -0400, David Joyner wrote:
> On Thu, Jul 31, 2014 at 2:45 PM, Thomas Feulner
> <thomas....@uni-bayreuth.de> wrote:
> > Dear David,
> >
> > it would be great, if someone could assist me. I am not working in academics
> > anymore and it is quite hard to find enough time for doing math in the
>
> I didn't know that. I told people you were still in academics:-(
>
> > evening. I already wrote a post on the list.
> >
>
> Thanks for that post.
>
> > Personally, I think that it is very dangerous for Sage to put everything
> > into its standard libraries. I think it would be much better to have a
> > modular concept.
> > Therefore, I would prefer to maintain my algorithm for canonical forms for
> > ring-linear codes in one single package. The ticket 13398 already shows,
> > that not too many mathematician seem to be interested in chain rings. We
> > have to ask ourselves, respectively the community: is the standard the right
> > place for codes over chain rings...?
> >
>
> Should this patch be changed to a python package which can be installed, then
> posted somewhere other than on the trac?
>
> Note that http://www.computeralgebra.uni-bayreuth.de/de/team/Feulner_Thomas/
> returns a 404 error, as does
> http://www.computeralgebra.uni-bayreuth.de/de/team/Feulner_Thomas/codecan-1_1_spkg.zip

this stuff can now be found in
http://www.computeralgebra.uni-bayreuth.de/de/team/z_former_members/Feulner_Thomas/index.html
namely
http://www.computeralgebra.uni-bayreuth.de/de/team/z_former_members/Feulner_Thomas/codecan.tar
and
http://www.computeralgebra.uni-bayreuth.de/de/team/z_former_members/Feulner_Thomas/codecan-1_1_spkg.zip

Just in case,
Dima