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 transparencies). 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 OhioLink if necessary) well in advance of the first deadline.
Time Line
1. Project Description/Proposal: Due date: Wed Apr 3 (Week 10). First choose a topic in Coding Theory or Cryptography. Below are some suggestions (and resources) about possible topics. Possibilities are great and you may choose a topic different from what is listed below. This 1-2 page proposal should include what you want to cover, and what sources you will be using and how, i.e. it should contain an annotated bibliography. It is important to make sure that your project is mathematically based, i.e, it must include (analyze/study/explain) mathematical foundations, it cannot only be about applications or implementation. Do not finalize your choice until you make sure that you have access to good sources.
2. Detailed Outline: Due date: Monday Apr 15 (Week 12). This should probably be 3 pages or so (the more, the better), and should include sections that will be included in the final paper, precise statements of theorems, sketches of proofs, and summaries of contextual or historical material. Include references.
3. Complete Draft: Due date: Wed Apr 24 (Week 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 Thu, May 9, 11:30 am (can turn it in earlier. Submit to Moodle.)
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. Make sure that your project is mathematically based. 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. [6],[13],[29],[36],[37], and a large number of papers and online tutorials. Here is one of the important papers.
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, related to DNA codes. [Start by looking at the papers in the Google drive.]
12. Locally Repairable Codes. [Start by looking at the papers in the Google drive.]
13. You can find ideas about computational/programming projects in [24] (for both coding theory and cryptography).
14. 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!).
15. 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 Google drive folder.
16. 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.
17. Quantum error correcting codes from classical codes. [Start by looking at the papers in the Google drive.]
18. There are other computational projects in coding theory (involving Magma). Talk to the professor if you are interested in doing a computational project.
.....................
Here is a topic that connects both disciplines.
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], [11], [35],[42] and the set of papers in the Google drive.
Cryptography
1. Secret Sharing Schemes. [1] and first edition of (1995) [11], [34]. There is a set of papers about secret sharing schemes from MDS codes in the Google drive.
2. Cryptographic Hash Functions. [5],[11], [16],[17],[29],[33],[35],[40], http://csrc.nist.gov/CryptoToolkit/tkhash.html
3. Integer Factoring Algorithms: [1],[5],[11], [16],[33], [34], [38].
4. Primality Tests and Prime Number Generation: [5], [11],[16],[17], [34], [38].
5. Elliptic Curve Cryptography: [1],[2],[5],[33], [34], [35], [38], [41].
6. Pseudo-Random Number Generation: [11], [16]. [17],[26].
7. Computational Complexity as it relates to Cryptography or Coding Theory: [16],[18]
8. Quantum Computation and (Quantum Error-Correcting Codes or Quantum Cryptography): [1], [2],[19],[23], [25], [34], [35].
9. Lattice based methods and NTRU cryptosystem. This is another candidate for post-quantum cryptography. [1], [11], [35],[41], [42]. See this paper.
10. Knapsack Cryptosystems
11. History of Cryptography (be sure to include sufficient mathematical content). See the relevant articles on this page. There is also more there.
12. Attacks on the RSA system. See the folder in google drive.
13. Attacks on the Discrete Logarithm Problem. See the folder in google drive.
14. Multivariate Cryptography, [11], [42]. This is also a candidate for post-quantum cryptography.
15. Mathematical basis of blockchain technology, bitcoin, and cryptocurrencies. This topic is heavily depended on digital signatures and hash functions.
16. Hash-based Digital Signature Schemes [11], [42].
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
Advances in Mathematics of Communication
Finite Fields and Their Applications
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.