Topic outline

  • CS-E4500 Advanced Course in Algorithms

    CS-E4500 Advanced Course in Algorithms

    Spring 2019: Algorithms for Polynomials and Integers


    This is an advanced-level optional course that in spring 2019 explores algorithm designs for univariate polynomials and large-integer arithmetic, with a three-fold motivation:

    1. The toolbox of near-linear-time algorithms for univariate polynomials and large integers provides a practical showcase of recurrent mathematical ideas in algorithm design such as linearity, duality, divide-and-conquer, dynamic programming, iteration and invariants, approximation, parameterization, tradeoffs between resources and objectives, and randomization.
    2. We gain exposure to a number of classical and recent applications, such as secret-sharing, error-correcting codes, probabilistically checkable proofs, and error-tolerant computation.
    3. A tantalizing open problem in the study of computation is whether one can factor large integers efficiently. We will explore select factoring algorithms both for univariate polynomials (over a finite field) and integers.


    Prerequisites: Fundamentals of algorithm design and analysis (e.g. CS-E3190). Mathematical maturity.

    Teacher: Prof. Petteri Kaski.

    First lecture: Tuesday 15 January 2019, 12--14, hall T5 (Konemiehentie 2).

    Grading: Points awarded from weekly problem sets determine the course grade. No exam.

    Learning objectives

    • Terminology and objectives of modern algorithmics, including elements of algebraic, approximation, online, and randomised algorithms. Ways of coping with uncertainty in computation, including error-correction and proofs of correctness.
    • The art of solving a large problem reduction to one or more smaller instances of the same or a related problem.
    • (Linear) independence, dependence, and their abstractions as enablers of efficient algorithms.
    • Making use of duality. Often a problem has a corresponding dual problem that is obtainable from the original (the primal) problem by means of an easy transformation. The primal and dual control each other, enabling an algorithm designer to use the interplay between the two representations.
    • Relaxation and tradeoffs between objectives and resources as design tools. Instead of computing the exact optimum solution at considerable cost, often a less costly but principled approximation suffices. Instead of the complete dual, often only a randomly chosen partial dual or other relaxation suffices to arrive at a solution with high probability.

    Synopsis of lectures

    Polynomials in one variable are among the most elementary and most useful mathematical objects, with broad-ranging applications from signal processing to error-correcting codes and advanced applications such as probabilistically checkable proofs. One of the main reasons why polynomials are useful in a myriad of applications is that highly efficient algorithms are known for computing with polynomials. These lectures introduce you to this near-linear-time toolbox and its select applications, with some algorithmic ideas dating back millennia, and some introduced only in the last few years.

    By virtue of the positional number system, algorithms for computing with polynomials are closely related to algorithms for computing with integers. In most cases, algorithms for polynomials are conceptually easier and thus form our principal object of study during our weekly lectures, with the corresponding algorithms for integers left for the exercises or for further study.

    A tantalizing case where the connection between polynomials and integers apparently breaks down occurs with factoring. Namely, it is known how to efficiently factor a given univariate polynomial over a finite field into its irreducible components, whereas no such algorithms are known for factoring a given integer into its prime factors. Indeed, the best known algorithms for factoring integers run in time that scales moderately exponentially in the number of digits in the input. These lectures introduce you both to efficient factoring algorithms for polynomials and to moderately exponential algorithms for factoring integers.

    Lecture schedule (tentative)

    • Lecture 1 (Tue 15 Jan): Polynomials and integers.
      We start with elementary computational tasks involving polynomials, such as polynomial addition, multiplication, division (quotient and remainder), greatest common divisor, evaluation, and interpolation. We observe that polynomials admit two natural representations: coefficient representation and evaluation representation. We encounter the more-than-2000-year-old algorithm of Euclid for computing a greatest common divisor. We observe the connection between polynomials in coefficient representation and integers represented in the positional number system.
    • Lecture 2 (Tue 22 Jan): The fast Fourier transform and fast multiplication.
      We derive one of the most fundamental and widely deployed algorithms in all of computing, namely the fast Fourier transform and its inverse. We explore the consequences of this near-linear-time-computable duality between the coefficient and evaluation representations of a polynomial. A key consequence is that we can multiply two polynomials in near-linear-time. We obtain an algorithm for integer multiplication by reduction to polynomial multiplication.
    • Lecture 3 (Tue 29 Jan): Quotient and remainder.
      We continue the development of the fast polynomial toolbox with near-linear-time polynomial division (quotient and remainder). The methodological protagonist for this lecture is Newton iteration. We explore Newton iteration and its convergence both in the continuous and in the discrete settings, including fast quotient and remainder over the integers.
    • Lecture 4 (Tue 5 Feb -- rescheduled to Thu 7 Feb): Batch evaluation and interpolation.
      We derive near-linear-time algorithms for batch evaluation and interpolation of polynomials using recursive remaindering along a subproduct tree. In terms of methodological principles, we encounter algebraic divide-and-conquer, dynamic programming, and space-time tradeoffs. As an application, we encounter secret sharing.
    • Lecture 5 (Tue 12 Feb): Extended Euclidean algorithm and interpolation from erroneous data.
      This lecture culminates our development of the near-linear-time toolbox for univariate polynomials. First, we develop a divide-and-conquer version of the extended Euclidean algorithm for polynomials that recursively truncates the inputs to achieve near-linear running time. Second, we present a near-linear-time polynomial interpolation algorithm that is robust to errors in the input data up to the information-theoretic maximum number of errors for correct recovery. As an application, we encounter Reed--Solomon error-correcting codes together with near-linear-time encoding and decoding algorithms.
    • Tue 19 Feb: Exam week, no lecture.
    • Lecture 6 (Tue 26 Feb): Identity testing and probabilistically checkable proofs.
      We investigate some further applications of the near-linear-time toolbox involving randomization in algorithm design and proof systems with probabilistic soundness. We find that the elementary fact that a low-degree nonzero polynomial has only a small number of roots enables us to (probabilistically) verify the correctness of intricate computations substantially faster than running the computation from scratch. Furthermore, we observe that proof preparation intrinsically tolerates errors by virtue of Reed--Solomon coding.
    • Tue 5 Mar: Break, no lecture.
    • Lecture 7 (Tue 12 Mar): Finite fields.
      This lecture develops basic theory of finite fields to enable our subsequent treatment of factoring algorithms. We recall finite fields of prime order, and extend to prime-power orders via irreducible polynomials. We establish Fermat's little theorem for finite fields and its extension to products of monic irreducible polynomials. We also revisit formal derivatives and taking roots of polynomials.
    • Lecture 8 (Tue 19 Mar): Factoring polynomials over finite fields.
      We develop an efficient factoring algorithm for univariate polynomials over a finite field by a sequence of reductions. First, we reduce to square-free factorization via formal derivatives and greatest common divisors. Then, we perform distinct-degree factorization of a square-free polynomial via the polynomial extension of Fermat's little theorem. Finally, we split to equal-degree irreducible factors using probabilistic splitting polynomials.
    • Lecture 9 (Tue 26 Mar): Factoring integers.
      While efficient factoring algorithms are known for polynomials, for integers the situation is more tantalizing in the sense that no efficient algorithms for factoring are known. This lecture looks at a selection of known algorithms with exponential and moderately exponential running times in the number of digits in the input. We start with elementary trial division, proceed to look at an algorithm of Pollard and Strassen that makes use of fast polynomial evaluation and interpolation, and finally develop Dixon's random squares method as an example of a randomized algorithm with moderately exponential expected running time.