Abstract Algebra in Theoretical Computer Science
The final exam is here.
Deadline: Midnight today (23/1).
In case needed, clarifications will be posted here. Before asking a question by emailing me, please check existing clarifications.
A practice exam can be found here.
A solution for Problem 7 on the practice exam can be found here. It is attached mainly for you to have a sense of the required level of formalism.
Course Pitch (a.k.a. Syllabus)
Theoretical computer scientists make an extensive use of elements from abstract algebra. From the design and analysis of algorithms and cryptographic protocols to the construction of desired combinatorial objects, the use of algebraic structures has repeatedly provided powerful and elegant solutions. Mastering the required mathematical background, however, requires isolating relevant parts from several courses in Mathematics or, alternatively, is done ad hoc.
This course provides a thorough introduction to abstract algebra, focusing on the useful elements required for the aforementioned use within computer science. In the first half of the course, we will study basic, frequently used, notions such as groups, rings, and finite fields. In the second part, we will consider more advanced notions from Commutative Algebra and Galois Theory. The math will be developed alongside applications in Theoretical Computer Science, Coding Theory, and Cryptography. We will take a bird's-eye view, focusing on the key notions and ideas while omitting some of the proofs. Some of the applications that will be discussed are:
Randomness mergers and the Kakeya Set problem
Private Information Retrieval schemes
Parvaresh–Vardy codes and the Guruswami-Umans-Vadhan expander graph
Who this course is for?
The target audience for the course is computer science graduate and advanced undergraduate students that would like to study fascinating mathematics and employ it in their research. No prior knowledge in math is required beyond basic linear algebra, combinatorics, probability theory and a basic course in algorithms on the CS side.
A follow-up course on Algebraic-Geometric Codes
In the spring semester, I will give a course on the fascinating subject of Algebraic-Geometric Codes of which the current course is a prerequisite.
When and where
Location: Dan David 111
Okay, look - I really like to keep things simple, but given the number of students enrolled to the course, we're gonna have to be creative. The grade consists of three parts - homework problems, scribing lecture notes, and a final take-home exam. The homework problems will not be graded (or handed for that matter). Instead, half of the questions on the exam will be a slight variant of questions from the homework. The other half will consist of new problems. The exam determines 2/3 of the final grade (so, effectively, 1/3 homework and 1/3 new questions on the exam), and 1/3 scribing notes. Each pair (or triplet, depending on the number of participants) will scribe a lecture in LaTeX, possibly filling some gaps that were left during the lecture. Here is an example of how the compiled lecture notes look in a previous course I gave. Here is part of the lecture notes I wrote for Lecture 2.
We will not follow any particular book. I plan on publishing lecture notes. However, below is a list of books for reference
Abstract Algebra / Herstein
Algebraic Number Theory / Stewart and Tall
and some of the papers we will cover
I also recommend reading Gadi Alexandrovich's truly fantastic blog (it's in Hebrew). It has clear and insightful lines of posts on Commutative Algebra, Galois Theory and Algebraic Number Theory (as well as on many other topics).
The following lecture notes (currently lectures 1-12) were taken by students that participate in the course. I didn't verify correctness etc yet so use at your own risk.
What have we done so far
Lecture 1 - Motivating examples
Four Motivating examples
Error correcting codes and the Reed Solomon code
Private information retrieval
Lecture 2 - Group theory
This and the next lecture are based on Chapter 2 from Herstein 3rd edition (or 2.1-2.7 from the 2nd edition).
A second look at the known extensions N,Z,Q,R,C
The fundamental theorem of algebra
Introduction to Group Theory
Definition, motivation, and examples
Cosets and Lagrange Theorem
Quotient groups and normal subgroups
Lecture 3 - Group theory continued
This and the previous lecture are based on Chapter 2 from Herstein 3rd edition (or 2.1-2.7 from the 2nd edition).
Cyclic groups and generated subgroups
Euler's formula and Fermat's little theorem
- Group isomorphism
Lecture 4 - Group theory continued and Ring theory
This lecture is mostly based on Herstein, Chapter 4.1-4.4.
The first homomorphism theorem (the rest are in the homework)
The correspondence theorem (aka the 4th homomorphism theorem)
The fundamental theorem of finite abelian groups (without a proof)
Basic concepts in rings
Finite fields of prime order
Ring homomorphisms and isomorphic rings
Principal ideal domains (PID)
Quotient rings and the 1st and 4th homomorphism theorems for rings
The Gaussian integers
A taste of additive combinatorics
Lecture 5 - Ring theory continued
This lecture is mostly based on Herstein, Chapter 4.4-4.7
Constructing ideals from existing ones
- Maximal ideals, prime ideals, and quotient by such ideals
- Playing with ideals in the Gaussian integers
Lecture 6 - Ring theory continued and Fields
This lecture is mostly based on Herstein, Chapter 4.5, 4.7.
- Gaussian integers and number fields that are not PID
- The field of fractions
- The polynomial ring
- Constructing finite fields from the polynomial ring
- Constructing the complex field
Lecture 7 - Ring theory continued and Fields
This lecture is mostly based on Herstein, Chapters 5.1, 5.3, 5.4.
- Field extensions
- Example: constructing the complex numbers
- Algebraic elements and transcendental elements
- Algebraic extensions
Lecture 8 - Fields and polynomials
This lecture is mostly based on Herstein, Chapters 5.4, 5.6.
- Finite extensions
- Adjoining an algebraic element to a field
- A closer look on polynomials and their roots
Lecture 9 - Finite fields and applications to small-bias sets
This lecture is mostly based on Herstein, Chapters 6.2, 6.3 and on papers on small-bias sets (see below).
- Classifying and constructing finite fields
- Small bias sets
- The AGHP construction (see paper).
Lecture 10 - Small-bias sets: the Ben Aroya - Ta-Shma construction
This lecture is based on the paper paper.
- The Hermitian curve
- Eisenstein criterion in general integral domains
- Bezout's theorem (without a proof)
- The Ben-Aroya Ta-Shma construction of small-bias sets (paper).
Lecture 11 - Randomness mergers via the polynomial method
- Wrapping up small-bias sets: an existence proof via the probabilistic method
- How to measure entropy
- Randomness mergers
- Merging two variables
- Merging many variables via the Curve Merger
Lecture 12 - Unbalanced expanders and randomness condensers
This lecture is based on this paper.
- Expander graphs
- The GUV construction
Lecture 13 - Tree codes
This lecture is based on this paper.
- Definition and motivation
- Proof of existence
- Explicit construction with poly-log alphabet size