Abstract Algebra in Theoretical Computer Science
Fall 2018
Final exam
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.
Practice final
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'seye 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 GuruswamiUmansVadhan 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 followup course on AlgebraicGeometric Codes
In the spring semester, I will give a course on the fascinating subject of AlgebraicGeometric Codes of which the current course is a prerequisite.
When and where
Thursday 10:0013:00
Location: Dan David 111
Grade
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 takehome 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.
Reading material
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).
Lecture notes
The following lecture notes (currently lectures 112) were taken by students that participate in the course. I didn't verify correctness etc yet so use at your own risk.
Assignments
What have we done so far
Lecture 1  Motivating examples

Four Motivating examples

Error correcting codes and the Reed Solomon code

Expander graphs

Private information retrieval

Randomness mergers

Lecture 2  Group theory
This and the next lecture are based on Chapter 2 from Herstein 3rd edition (or 2.12.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

Commutativity

Direct product

Subgroups

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.12.7 from the 2nd edition).

Cyclic groups and generated subgroups

Euler's formula and Fermat's little theorem

Cauchy's theorem
 Homomorphisms
 Group isomorphism
 Kernel
Lecture 4  Group theory continued and Ring theory
This lecture is mostly based on Herstein, Chapter 4.14.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

Rings

Commutative rings

Zero divisors

integral domains

Fields

Basic properties


Finite fields of prime order

Ring homomorphisms and isomorphic rings

Ideals

Principal ideals

Principal ideal domains (PID)

Quotient rings and the 1st and 4th homomorphism theorems for rings

Maximal ideals

The Gaussian integers

A taste of additive combinatorics
Lecture 5  Ring theory continued
This lecture is mostly based on Herstein, Chapter 4.44.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.
You are also encouraged to read Gadi's great blog posts on fields. The ones related to what we cover in this lecture are here, here and here.
 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 smallbias sets
This lecture is mostly based on Herstein, Chapters 6.2, 6.3 and on papers on smallbias sets (see below).
 Classifying and constructing finite fields
 Small bias sets
 The AGHP construction (see paper).
Lecture 10  Smallbias sets: the Ben Aroya  TaShma 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 BenAroya TaShma construction of smallbias sets (paper).
Lecture 11  Randomness mergers via the polynomial method
This lecture is based on a sequence of papers: this, this, and that.
 Wrapping up smallbias 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 polylog alphabet size