Information and Resources for the Final Project

Read these articles on "how to give a good math talk" Article1, Article 2, Article 3, A Summary of Important Points. This web site is also very useful. It is specifically designed to help people give good math talks.

The first two articles are by the same authors, and the second one is an update on the first one (the first one was published in 1998 when most talks were by overhead transperencies). You may want to start with the second article.

Important Note: Please do not choose a topic without looking at resources first. Therefore, get some books (order them from Ohio link if necessary) well in advance of the first deadline.

Time Line

1. Project Description: Due date: Thu Apr 4 (W 10). First choose a topic in Coding Theory or Cryptography. Below are some suggestions (and resources) about possible topics, but you may choose a different topic. This one-page outline should include what you want to cover, and what sources you will be using and how, i.e. it should contain an annotated bibliography.

2. Detailed Outline: Due date: Tue Apr 16 (W 12). This should probably be 3 pages or so (the more, the better), and should include precise statements of theorems, sketches of proofs, and summaries of contextual or historical material. Include references.

3. Complete Draft: Due date: Thu Apr 25 (W 13). This should be a complete draft of your paper. It must contain all proofs and details.

4. In-class presentations. During the last week of class

5. The final paper: Due Wed, May 8, 1:30 pm (can turn it in earlier. Submit electronically as an email attachment.)

Ideas About Possible Topics

Here is a list of some possible topics, with references as a starting point. You can also find a lot of resources on the internet.Your topic does not have to be one of these, you can choose a different topic. Some of these topics are covered in our textbook. If you choose a topic that is in the textbook, you must use other resources as well. In general, you should use several different sources. Accuracy and correctness are crucial. Give complete and careful references, do not plagiarize. The numbers for references refer to the list of resources at the end of the course syllabus. Although not strictly required, you are encouraged to include computations or computer searches with Magma (or other software) in your project.

The list below is in no particular order and it is subject to change.

Coding Theory

0. Bounds on the parameters of a code that we did not discuss in class such as Griesmer, Linear Programming, Plotkin bounds and others. Can be found in most coding theory books, e.g. [32], [10],[9],[14].

1. Weight Enumerators and MacWilliam's identity. This is a well-known and fundamental theorem in coding theory relating weight enumerator of a code to its dual. Can be found in most coding theory books but there is a more accessible proof in [14]. You may include material on self-dual codes.

2. BCH Codes and their decoding. Can be found in most coding theory books.

3. Reed Solomon Codes and their decoding. Can be found in most coding theory books.

4. Codes and Designs (combinatorial designs). Steiner triple system from the Golay code (one of the many wonderful things about the Golay code) Start with [3] and [6]. Connections of Golay codes to other areas of mathematics.

5. Codes over Z_4. [3], [6], [9].

6. Convolutional Codes. [9], [6],[13],[15],[21],[27]

7. Low Density Parity Check (LDPC) Codes. [13]

8. Quadratic Residue Codes: [3],[6], [9],[10],[14].

9. Reed-Muller Codes. Can be found in most coding theory books.

10. Games and Codes, Lexicodes: [3],[22] and this paper, and this one. This project may involve a programming part to generate lexicodes.

11. Reversible Codes and Their Applications.

12. Locally Repairable Codes

13. You can find ideas about computational/programming projects in [24] (for both coding theory and cryptography).

14. Also see these web pages [22] for more ideas and tips for Mapla/Magma programming: 1, 2, 3

15. Exhaustive searches for cyclic or constacyclic codes over various fields. This paper, which is the outcome of the summer science research of Kenyon student in summer 2013, is a good one to start with. There is a possibility that you may discover record breaking codes (in that case you will be mentioned on the table of best known codes and became famous, at least in coding theory community!).

16. Quasi-cyclic and quasi-twisted codes. A generalization of cyclic codes that contain many good codes. Many of the best known codes are from this family. After describing their structure, it may be possible to search for new codes from this class and possibly find some new, record breakingcodes! (in that case you will be mentioned on the table of best known codes). Start with these papers 1, 2, (parts of the chapter) 3 Also, there is a set of papers in the P drive.

17. Skew-cyclic codes. These are also a generalization of cyclic codes but they live in a non-commutative algebraic structure known as skew polynomial ring. These codes are recenty introduced in 1 and they are known to contain good codes 2. They are also related to quasi-cyclic codes 3.

18. There are other computational projects in coding theory (involving Magma). Talk to the professor if you are interested in doing a computational project.

.....................

Code-Based Cryptography: This is an active area of research that combines coding theory and cryptography in an interesting way. See section 18.10 in Trappe & Washington [1], and the set of papers in the P drive.

Cryptography

1. Secret Sharing Schemes. [1] and first edition of (1995) [11]. There is a set of papers about secret sharing schemes from MDS codes in the P drive.

2. Cryptographic Hash Functions. [5],[11], [16],[17],[33] http://csrc.nist.gov/CryptoToolkit/tkhash.html

3. Integer Factoring Algorithms: [1],[5],[11], [16],[33].

4. Primality Tests and Prime Number Generation: [5], [11],[16],[17].

5. Elliptic Curve Cryptography: [1],[5],[33]

6. Pseudo-Random Number Generation: [11], [16]. [17],[26].

7. Computational Complexity: [16],[18]

8. Quantum Computation and (Quantum Error-Correcting Codes or Quantum Cryptography): [1], [19],[23], [25].

9. Lattice based methods and NTRU cryptosystem. This is another candidate for post-quantim cryptography. Starting point: Chapter 17 of Trappe & Washington [1].

10. NTRU: http://www.ntru.com

11. Knapsack Cryptosystems

12. History of Cryptography (be sure to include sufficient mathematical content). See the relevant articles on this page. There is also more there.

13. Attacks on the RSA system.

14. Attacks on the Discrete Logarithm Problem.

15. Blockchain technology and bit coins. This topic heavily depends on digital signatures and hash functions.

16. There are many possible topics and links on this page.

....................

Database

Search the Ohio Link for additional resources (or locating the resources listed above).

Use the search engine of MathSciNet to find articles on particular topics, or particular articles referenced in other articles.

Journals

Designs, Codes and Cryptography

Journal of Cryptology

Advances in Mathematics of Communication

One of the most important journals for information theory is IEEE Transactions on Information Theory. You don't have access to it. If you need any articles from that journal, let me know.