Basic Information

• What is this course about?: The past decade has seen a lot of applications of Algorithmic techniques related to Algebraic structures in various sub-areas of theoretical computer science. In particular, areas like Algorithms, Computational Geometry, Cryptography and Complexity Theory have benefited immensely from these algorithmic techniques. This course aims to introduce these algorithms and some of their applications in a systematic manner. We will be particularly focussing on algorithmic problems and techniques related to polynomials.


• Syllabus? :
  • Introduction : Motivation to study algorithmic problems related to polynmials - overview of example applications. The language - Rings, Fields, Ideals, and Polynomials.
  • Algorithms for Polynomials . Algorithm for GCD: Euclid’s algorithm. Hilbert’s basis theorem. Solving polynomial equations; ideal membership problem; Grӧbner bases: Buchberger’s algorithm. Polynomial factorization over finite Fields: Cantor Zassenhaus Algorithm, applications to root finding. Hensel lifting and applications to polynomial factorization: Zassenhaus Algorithm. Lattices, and LLL algorithm for basis reduction.
  • Complexity of Polynomials: Basic Arithmetic Circuit Complexity. Polynomial Identity Testing problem; Applications to Primality Testing: AKS Primality test; Introduction to Algebraic Complexity. Polynomial and Matrix Multiplication Problems, Permanent vs Determinant problem and connections to Polynomial Identity Testing.
  • Algorithmic Coding Theory: Basic definitions: Distance, Rate, Bounds. Reed Solomon Codes, Reed Muller Codes. List decoding. Local decoding. Local-list decoding.


• Target audience? Pre-requisites? : Any student who is interested in algebra and computation and having basic discrete mathematics training. We will be quickly covering (indeed, some of them may be left as small reading assignments) the basic algebra needed and get to the "algorithmic part". But the course is intended to be "more-or-less" self-contained. The course is intended to be reaching out students who would wish to see algorithmic ideas borrowed from and applied to rich algebraic structures.
  
  On a first look at the name and the contents, this course might look a bit difficult because of many reasons - 1) the term "algebra" in the name sends people off, 2) the term "complexity" in the syllabus sends people off. If you are worried about pre-requisites, read the section above. And, if you managed to convince yourself to take this course, congratulations - you seem to be on the right track! :-).


• (Unsolicited) Advice? : Now that you are in, here are some thoughts which from our experience with this course (as students), will help to get the maximum benefit out of it.
  • Keep at it, Don't fall behind ! - In a conceptual and deeply mathematical course like this, it takes time for ideas and terminologies to sink in and become a part of your easy language and thought process. This is particularly important in the beginning where more of algebraic concepts will be introduced. It is extremely important to put in consistent effort throughout the semester, rather than hoping to learn everything together at the end, right before the deadlines or tests. Even though we divide the course into themes, the ideas are so inexplicably connected across themes. So, even missing a few lectures, can cause difficulty.
  • Solve the problems from the problem sets ! - The problems in the problem sets are handpicked in order to ensure that you complete the thought process started in the lectures.
    A suggestion: Here is a useful scheme to work on the problem sets. Start working on the problem sets by yourself as soon as they are available. Think through possible approaches during your spare time, say while you are waiting in line (if you do !) at canteen/mess. The earlier you start the more mature the thoughts will become before the deadline.
    About 3-4 days before the deadline, identify the problems that you think you might not be on the right track and talking to someone might help (at the expense of 20% of the credit - see below). Collect your thoughts (and mind-blocks) on those problems in a sheet of paper (consider this as a read only tape) - and hold a meeting with your partner for a discussion. The tape/paper is read-only - so the conversation and the details of it will not be (and should not be) recorded. After the discussion, reproduce, on your own, the ideas which helped you get over your mind-blocks and of course cite the source. This will naturally avoid plagiarism and you definitely will learn the solution and the reason it gets you over the mindblock.
    Make sure you submit before the deadline even if you could not solve all the problems. There will be discussion sessions for problem sets.
  
  
• Policy Matters :
  
  Here are some policy matters regarding problem sets :
  • Policy regarding Collaboration: Collaboration is allowed. The idea is to encourage collaboration on the harder problems (you should not collaborate on problems which you would be able to solve by yourselves), and encourage collaborations which has roughly an equal contribution from the participants. It is also a principle that one who solves the problem on his/her own should get the maximum credit. Based on this view, here are the rules of the game.
    • It is a strict rule that, even after collaboration the answer should be written individually and independently. Referring to any other source than text books, class reference materials/links and your CS6842-mates is not allowed.
    • At most one collaborator is allowed for each problem in a problems set. The submission must contain, for each problem, the name of the collaborator whom you worked with and this should be reciprocated in your collaborator's submission. If inconsistencies are found, then both the submissions become invalid.
    • Collaborated solutions will be charged 20% of it's score.
    • The scheme is entirely based on trust. If two people collaborate and chose not to write the collaborators name - this scheme is not designed to respond. However, if detected (there might be random checks of various forms), the penalty for such unethical practices and plagiarism in submissions is extremely high (even if a reference to the original source is given).
  
  
  • Late Penalty: 5 days from the deadline is the maximum delay allowed. This is set to be so because, otherwise the evaluation will be a never-ending process. Submissions will not be penalized if the delay is less than two days. The next three days will be charged 10% of the marks for each day (marks will not become negative).