DD2442 Seminars on Theoretical Computer Science Autumn 2014: Algebraic Gems in TCS

Follow these shortcut links to go directly to news, short overview of course, schedule, lecturers, prerequisites, learning outcomes, examination, course material, problem set info (with a description of the peer evaluation grading process and a list of the actual psets), or links.

This webpage provides all documentation and information about the course, so there is no separate course memo ("kurs-PM") PDF file.

In the last few decades, algebraic methods have played an important role in theoretical computer science. Many recent important results in different areas have been obtained by strikingly elegant proofs using very simple properties of polynomials and linear algebra. This progress has also underlined the importance of improving our understanding of such algebraic properties.

The purpose of this course is to survey a selection of interesting (and often surprising) applications of linear algebra and polynomials to problems in combinatorics, complexity theory, and algorithm design. The algebraic tools needed are developed along the way.

A list of questions that we wanted to study (but which, as expected, turned out to be somewhat optimistic) is as follows:

Ramsey graphs: How large can graphs be without containing cliques or independent sets of some given size?
Expander graphs: How can one construct very sparse graphs that are essentially as well-connected as complete graphs?
Error-correcting codes: How can one transmit messages reliably over a noisy channel?
Circuit complexity: How can one prove lower bounds on circuits computing Boolean functions?
Interactive and probabilistically checkable proofs: How can interaction between computational agents be used to exactly characterize classical complexity classes?
Kakeya conjecture for finite fields: How large must a set of vectors be to contain a line in every direction in a vector space?
Low-degree testing: Given a (huge) function table for a multivariate function, is it possible to probe the table in just a few positions and decide with high confidence whether the function is a low-degree polynomial or not?
Polynomial identity testing: Very efficient probabilistic methods are known to test whether two polynomials are the same, but is there a way to do this deterministically?

Schedule

This course was given in periods 1-2 in the autumn of 2014. It We had a total of 21 lectures, with 2 lectures per week on average. In accordance with the academic quarter tradition at KTH, 10 am in the schedule below actually means 10:15 am et cetera. See the list of rooms at KTH to locate the different lecture rooms.

Weekday	Date	Time	Room	#	Plan of lectures	References
Tue	Sep 16	10-12	L21	1.	Course overview; practicalities; abstract algebra recap	notes
Thu	Sep 18	13-15	B21	2.	Linear algebra recap; odd/even town; Fisher's inequality	notes
Tue	Sep 23	13-15	1625	3.	Ramsey graphs	notes
Thu	Sep 25	13-15	4523	4.	Intro to spectral graph theory, Hoffman's theorem, random walks on graphs	notes
Tue	Sep 30	13-15	1537	5.	Definition of expander graphs, Expander mixing lemma, Cheeger inequalities	[AB09] Ch 21, notes
Thu	Oct 2	13-15	4523	6.	Efficient randomness reduction, explicit construction of expander graphs	[AB09] Ch 21, notes
Tue	Oct 7	13-15	1537	7.	Explicit construction of expander graphs (cont.)	[AB09] Ch 21, notes
Thu	Oct 9	13-15	1537	8.	Introduction to error-correcting codes, linear codes, Hamming code, Hamming bound	[Sud01] Lecs 2-3, notes
Thu	Oct 30	13-15	1537	9.	Singleton bound, Reed-Solomon & Reed-Muller codes, intro to algebraic complexity theory	[Sud01] Lec 4, notes
Tue	Nov 4	13-15	1537	10.	Guest lecture by Michael Forbes: Polynomial identity testing I	notes for both lectures
Thu	Nov 6	13-15	1537	11.	Guest lecture by Michael Forbes: Polynomial identity testing II
Tue	Nov 11	13-15	1537	12.	Hadamard codes, Gilbert-Varshamov bound, code concatenation	[Sud01] Lecs 5-6, notes
Thu	Nov 13	13-15	1537	13.	Decoding, Welch-Berlekamp algorithm for RS codes, LDPC codes	[Sud01] Lec 10, notes
Tue	Nov 18	13-15	1537	14.	Asymptotically good LDPC codes with linear-time decoding	[HLW06] Sec 12, notes
Thu	Nov 20	13-15	4523	15.	Kakeya sets in finite fields	[Dvi09], notes
Tue	Nov 25	13-15	4523	16.	More about Kakeya sets & method of multiplicities I	[DKSS13], notes
Thu	Nov 27	13-15	1625	17.	More about Kakeya sets & method of multiplicities II	[DKSS13], notes
Tue	Dec 2	13-15	1625	18.	Almost optimal testing of low-degree polynomials I	[AKK+05], notes
Thu	Dec 4	13-15	1537	19.	Almost optimal testing of low-degree polynomials II	[AKK+05], notes
Tue	Dec 9	13-15	4423	20.	Optimal testing of low-degree polynomials I	[BKS+09], notes
Thu	Dec 11	13-15	1537	21.	Optimal testing of low-degree polynomials II	[BKS+09], notes

Lecturers

The main lecturer on the course is Jakob Nordström, who is responsible for all aspects of the course.

Michael Forbes from the Simons Institute for the Theory of Computing at UC Berkeley gave two guest lectures on the course.

We are using Piazza for teacher-student interaction on the course. Thus, questions should not be e-mailed to the lecturer, but instead posted on Piazza (where you can send private notes to the instructor if needed, and also ask questions anonymously).

All course participants should be signed up at Piazza to receive all announcements related to the course (but note that this does not replace the official course registration at KTH).

Prerequisites

The course is open to anyone, but the main target audience are advanced Master's students and PhD students in computer science and mathematics. There is no need to register beforehand—you can just show up at the first lecture (or send an e-mail to the instructor if you have questions). You will need to formally register for the course in order for the instructor to be able to report your results, however. As of the autumn term 2013, students at KTH CSC should register via the "personal menu" ("personliga menyn" in Swedish), which was previously known as "my pages" ("mina sidor"). This replaces the registration previously done via the rapp.csc.kth.se system. Many different categories of students take this course, however, and might face different administrative problems. Please make sure that you also get registered as appropriate for your study program.

The formal requirements as stated on the Study Handbook webpage are that you should have taken DD1352 Algorithms, Data Structures, and Complexity or DD2352 Algorithms and Complexity or corresponding courses at other universities, but actually most of what we do will be independent of this material. You will need to know some probability theory and basic linear algebra, and some knowledge of abstract algebra (groups, rings, and fields) will also be helpful, although we will review briefly all concepts that we will need.

The lectures will be given in English.

Although the formal prerequisites are very limited, you will need mathematical maturity and a willingness to learn new stuff. It should be noted that this will be a somewhat demanding course. (But hopefully even more fun!)

Formal Learning Outcomes

After having completed the course, the student should be able to:

Define and motivate basic concepts covered by the course and explain how these concepts are related to one another.
Describe some important research results in modern theoretical computer science obtained by algebraic methods.
Use tools and techniques as covered by the course to prove basic theorems and independently solve problems amenable to these methods.
Present theoretical computer science arguments with mathematical stringency orally and in writing.
For the highest grade: read and understand a research article in theoretical computer science in an area covered by the course, and display this understanding by giving an oral presentation of the paper.

Examination

To pass the course, students will be required to solve and hand in solutions to three problem sets. The scores on the problem sets are what will mainly determine the final grades on the course (except as explained below).

For each each problem set, each student will also have to evaluate the solutions of a fellow student (but not assign grades), who will be randomly chosen by the instructor. This part of the examination will only be pass/fail as discussed in the description of the grading process below.

If you are a PhD student, you can take this course as a research-level doctoral course with a different course code. The requirements are slightly tougher and the grading is only pass/fail, but the course counts fully towards the course credit requirements in the PhD program.

The grades for Master's students taking DD2442 are determined according to the following principles:

To pass the course, you need a pass (E) on all problem sets. The score needed for an E or higher grades will be stated on each individual problem set. For each pset, you also need to evaluate the solutions of a fellow student.
In principle, the final grade will be the arithmetic mean of the grades for all the problem sets (except that there is an extra requirement for A as explained below). That is, think of A-E as {5,4,3,2,1}, sum up, and divide by the number of psets.
If this mean is not integral, later psets will affect the rounding more than earlier psets. Also, if you have done a good job of evaluating pset solutions by fellow students, this will affect the rounding upwards.
In order to get an A, you need to (a) obtain an average A or B on the problem sets and (b) read and present a research article in complexity theory (to be determined in consultation with the lecturer). The presentation should show that you have grasped the main contributions of the article, even though there probably will not be time to give detailed explanations of all the steps in the proofs. (Some helpful advice can be found in Ian Parberry's Speaker's Guide.)
It is very possible that there will be some corner cases that this set of rules (or any set of rules of reasonable length), cannot exactly capture. In such cases, we will strive to be generous rather than stingy.

For PhD students taking the research-level course, in addition to fulfilling the above requirements the average grade on the problem sets should be at least C and the oral presentation of a research article is mandatory. PhD students also have the option to take the Master's level course.

Note that solutions to the problem sets should be handed in strictly by the deadlines. Being able to work towards a deadline and deliver the best possible result within a given time frame (rather than a 100% polished product that arrives too late) is an important skill, and is something that you will have the opportunity to practise during the course. Having said that, exceptional circumstances, such as severe illness, can be accepted as an excuse for late problem set solutions. It should be emphasized, however, that lack of time due to work outside the university or due to many parallel courses is not considered as a legitimate reason for handing in problem set solutions late.

The KTH CSC code of honour applies to all aspects of this course including the problem sets. There are also some additional rules specific to (the problem sets of) this course. These rules are available below on this webpage and are stated on each problem set

Course Material

Note that the information below about course material will be updated as we go along.

The course has no official textbook. Below follows some information about books and articles that might be useful for participants on the course. Note also that there are links to handwritten notes for the lectures in the schedule.

Books, Surveys and Lecture Notes

Some of the material that we will cover can be found in:

[AB09] Sanjeev Arora and Boaz Barak: Computational Complexity: A Modern Approach.
[HLW06] Shlomo Hoory, Nathan Linial, and Avi Wigderson: Expander Graphs and Their Applications .
[Sud98] Madhu Sudan: Algebra and Computation, lecture notes.
[Sud01] Madhu Sudan: Algorithmic Introduction to Coding Theory, lecture notes.

Two good references for a more detailed background and further reading on some topics are:

[LN97] Rudolf Lidl and Harald Niederreiter: Finite Fields.
[Sho08] Victor Shoup: A Computational Introduction to Number Theory and Algebra.

Note, however, that these latter two references go into way more detail than we will have time to do during this course.

Research Articles

Especially during the second half of the course, some lectures will be based on research articles. Below follows a list of links to these articles. The intention is that the lectures will cover the material in the papers that we need, so students are not expected or required to read these papers (especially since some problems on the problem sets involves working out details in the papers that we did not have time to cover in class). The references below are provided only for completeness and for students interested in further reading.

[AKK+05] Noga Alon, Tali Kaufman, Michael Krivelevich, Simon Litsyn, and Dana Ron: Testing Reed-Muller codes.
[BKS+09] Arnab Bhattacharyya, Swastik Kopparty, Grant Schoenebeck, Madhu Sudan, and David Zuckerman: Optimal Testing of Reed-Muller Codes.
[DKSS13] Zeev Dvir, Swastik Kopparty, Shubhangi Saraf, and Madhu Sudan: Extensions to the Method of Multiplicities, with Applications to Kakeya Sets and Mergers.
[Dvi09] Zeev Dvir: On the Size of Kakeya Sets in Finite Fields.

Note that if you are not at KTH, or if you are connected to the KTH network via wireless, then you might not be able to access the PDF files with the articles linked to above. One way around this problem is to search for the titles of the papers in your favourite search engine—this should hopefully help you find free versions of the same papers on the webpages of the authors or similar. Another, often better, solution to this problem (courtesy of Lars Arvestad) is to invoke the KTH library proxy server directly in the address field of the browser. You do this by adding .focus.lib.kth.se to the domain of the web address where you found the paper in question, which will work if the KTH library has a subscription (this is usually the case). For instance, if you want to look at http://www.journal.com/somepaper.html but this paper is behind a pay-wall, you try to change the URL to http://www.journal.com.focus.lib.kth.se/somepaper.html. Supposing that the KTH library is paying for the journal in question, this should take you to the paper via a login page for your KTH account.

Problem Sets

General Information

Solutions to the problems sets should be submitted as PDF files by e-mail to jakobn at kth dot se. Please use the subject line Problem set <N>: <your name> and name the PDF file PS<N>_<YourName>.pdf with any national characters converted to standard ASCII (so the solutions to the second problem set by the main lecturer would have the file name PS2_JakobNordstrom.pdf, for instance). Solutions should be typeset in some math-aware system (read: LaTeX or such like; MS Word with Equation Editor is borderline but might pass). Please try to be precise and to the point in your solutions and refrain from vague statements. Some of the problems in the problem sets are meant to be quite challenging and you are not necessarily expected to solve all of them.

When you are working on the problem sets, discussions of ideas in groups of two are allowed, but you should always write down your own solution individually and understand all aspects of it fully. You should also acknowledge any collaboration. For each problem set, state at the beginning if you have been collaborating and with whom.

You can (and should) ask the instructor if anything about the problem sets is unclear. Make sure to post private messages to the instructor on Piazza in that case, so that your questions do not accidentally give away unintended information about the problems to the other students. If there is some issue needing clarification regarding some problem, the instructor will make a public post on Piazza.

Some of the problems are "classic" and hence it might be easy to find solutions on the Internet, in textbooks or in research papers. It is not allowed to use such material in any way unless explicitly stated otherwise. You can, however, use in your solutions anything said during the lectures on in the lecture notes, unless you are specifically asked to show something that we claimed without proof in class. It is hard to pin down 100% formal rules on what all this means—when in doubt, ask the lecturer.

Grading Process

We will try out a new approach for the seminar course this year which will involved some peer evaluation (and hopefully tons of interaction among the students). All final grading will be done by the instructor, however. Here is how it is intended to work.

Step 1: Work on the Problem Set

Students solve the problem set, on their own or collaborating in pairs, and write down their own solutions and submit as a PDF file by e-mail before the deadline. During this phase no discussion of problem set solutions is allowed other than with the collaborating partner (but sending a private message on Piazza to the instructor asking for clarifications is of course OK).

Step 2: Discussion of Solutions

After the deadline, the instructor distributes the problem set solutions randomly to the students as PDF files by e-mail. All students will have a day or two to go over the received problem set solutions, compare with their own solutions, and try to figure out what might be good or bad approaches to solving the various problems on the problem set.

When a day or two has passed, the instructor gives the start signal for discussions of solutions to the problems on Piazza. During this phase all students on the course should work together to find solutions (possibly many different ones) to all problems on the problem set.

During the discussions a maximum of collaboration is allowed and encouraged. There is no incentive not to collaborate here since nothing that happens after this point can lower the grade of any student. Instead, there will be bonus points for writing down correct solutions on Piazza, as well as for helping to improve on not fully correct or complete solutions. Note that a student need not have solved the problem him- or herself in order to contribute a solution on Piazza. It is sufficient to have understood and be able to present a solution. (However, just quoting from the received set of solutions verbatim is not encouraged—the bonus points are meant to award understanding, not copying skills.)

The instructor will not take part too actively in the exchange of comments, but will try to nudge the discussions in the right direction if need be.

Step 3: Peer Evaluation

Simultaneously, and using material learned during the discussion phase, each student should evaluate all the solutions in the set of received problem set solutions and write down comments on a print-out.

Here is how the solutions should be evaluated:

Each problem solved should be clearly marked as "correct", "incorrect", or "unknown".
For a "correct" solution, the key steps in the solution should be highlighted.
For an "incorrect" solution, the error(s) in the solution should be pointed out together with an explanation what the mistake is.
If a solution is truly unintelligible, it can be marked as "unknown" and a comment should be provided explaining where the evaluating student gets lost and why. Note, however, that hard-to-understand solutions can be discussed on Piazza (while giving a suitable amount of details in order to maintain the anonymity of both the student being evaluated and the student evaluating), and so this "unknown" option is expected to be very rare.
General comments discussing possible strong and weak points with the solution are encouraged—please use the opportunity to provide constructive feed-back to a fellow student.
At all times, please avoid harsh language and excessive criticism. Be polite and try to find not only negative but also positive aspects of the solutions.
All comments should be clearly legible. Shorter comments should be provided directly on the print-out. Longer comments can be provided on separate sheets of paper where it is clearly marked which comments pertain to which problem solution and where.

The solutions together with the evaluation comments should be should be put in the lecturer's mailbox on the 4th floor at Osquars backe 2 or handed to the lecturer before beginning of class on the day of the peer evaluation deadline.

Step 4: Final Grading

Finally, the lecturer will grade all problem set solutions and assign scores, and will at the same time evaluate the evaluations. Each student will receive both the instructor grading comments and the peer evaluation copy.

The problem set will be regarded as a pass if it reaches the threshold for E as specified in the problem set.

The problem set evaluation will be regarded as a pass if at least 50% of the solutions marked as "correct" or "incorrect" are properly identified as such (with relevant explanations), and if no solution is marked "unknown" unless there is a convincing explanation as to why this solution was not possible to understand. In particular, the lecturer might look at the discussions at Piazza to check if the student has made a good faith effort to get help to figure out what is going on in the solution.

Motivation for this Set-up

There are a number of reasons why this approach will be used. It is intended to:

Increase the coverage of the material, so that all students will work on (essentially) all problems regardless of whether they managed to solve them themselves or not.
Increase in-depth learning, in that students will have to really understand the problems in order to assess someone else's solutions.
Encourage students to write clearly and intelligibly, so that the text can be understood by their peers.
Help students develop the skills to read and understand mathematical arguments as presented by others.
Increase the amount of feed-back provided to each student, in that more individualized comments will be provided than can possibly be done by a single instructor marking all solutions.
Help the students internalize the course requirements, in that they will gain a greater understanding of what is an appropriate level of detail in the solutions, what is a suitable level of mathematical rigour in the arguments, what makes solutions easy or hard to read, and how this all affects the grading of the solutions.

As a side effect, this process might also help in the final grading of the problem set solutions by the instructor, although based on previous experience this effect is fairly limited.

This new approach will be thoroughly evaluated during (and certainly after) the course, and might be modified based on the conclusions from such evaluations. One of the reasons we are doing this is that a similar approach was used for the course DD2446 Complexity Theory and received overall very positive reviews. If you have any views or comments already now, feel free to contact the instructor on Piazza or by e-mail.

List of Problem Sets

Problem set 1 (last revised October 16, 2014): Deadline Thursday October 30. Peer evaluation due Tuesday November 11.
Problem set 2 (last revised December 12, 2014): Deadline Sunday December 14. Peer evaluation due Friday December 19.
Problem set 3 (last revised December 20, 2014): Deadline Friday January 16. Peer evaluation due Friday January 23.