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'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

Thursday 10:00-13: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 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.

 

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

 

• 2-Server PIR with Sub-Polynomial Communication

• On the Size of Kakeya Sets in Finite Fields

• Unbalanced Expanders and Randomness Extractors from Parvaresh–Vardy Codes 

 

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 1-12) were taken by students that participate in the course. I didn't verify correctness etc yet so use at your own risk.​

 

 

Assignments

• Assignment 1 - Group theory

• Assignment 2 - Ring theory

• Assignment 3 - The polynomial ring and fields

• Assignment 4 - Applications to TCS

 

 

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.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

  • 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.1-2.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.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

  • 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.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.

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 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

This lecture is based on a sequence of papers: this, this, and that.

• 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