professor
Allison Lewko

I love cryptography, and generally appreciated Allison's lectures. But I was not impressed by this class. To start, there was just too little material. Between meeting once a week and spending half of the class time on a dubious "design" project, we covered only a few topics, and only at a cursory level. The selection of topics was ok: identity based encryption, bilinear groups, byzantine agreement, differential privacy, fully homomorphic encryption, and obfuscation. However, there was no unifying theme; some of these topics are barely even cryptography. I felt like I learned a few neat cryptographic schemes, but did not come away from the class with anything else. There were no assignments aside from working on the design project. We were given papers to read; however, they were simply too long and hard to read in their entirety. I would have much preferred problems to do or more material to read on the basics. Because there were no assignments or exams, no one tried particularly hard to understand the material. The project mentioned above was to design an interactive protocol for key-exchange. The project was well-motivated: we read an attack paper that described a real-life attack against an existing scheme, and started brainstorming how to circumvent the problem. However, after that, we got kind of bogged down. A handful of student presented ideas, but after that, progress more or less halted. Yet we still spent half of the class re-hashing the problem.

I have mixed feelings about this course. It repeats a ton of material from Data Structures, more or less on the same level. There is some new material, but it doesn't feel like a semester's worth. Overall, the material was not particularly interesting. I guess you learn all the standard algorithms you should know: the theory of divide-and-conquer and greedy algorithms, then some classic sorts and graph algorithms. The lectures were fine. A little slow, but presented reasonably. The slides are online, which is nice, and the textbook is pretty standard. The level of rigour was adequate. However, the homeworks were painful. The problems themselves were not hard, but the TAs were brutal. They often complain about a supposed "lack of rigour". In a good math of theory class, you're supposed to write however much you need to show what you know. But in this class, you're supposed to write however much you need to show a toddler how to do it themselves. This felt like a waste of time for the students and the graders. The exams were graded much more forgivingly, though.

Well organized notes, very straightforward exams - very similar to the practice questions she provides. Probably one of the nicest professors on Columbia's campus. Office hours incredibly helpful.