Omri Weinstein

Easy homework, brutal exams (mind you, that's like 80% of your grade)

4 homework assignments 1 lecture to scribe 1 final project based on reading and original research

The class is basically taught and graded entirely by the TAs who do not know how to grade. Grading was always late (2 of the 5 homework assignments were graded after the final exam) and feedback was terse. Omri doesn't seem to care about his students because he's too busy doing other things. Many times he wouldn't be in his office during his office hours. Take this class with other professors who will actually take their job seriously.

So I took this course with Omri and he uses the textbook Computational Complexity: A Modern Approach. The course has its pros and cons. Look, Omri certainly knows the material but he is glued to the textbook. As I understand it he graduated from Princeton and thinks this book is the bees knees – the author is a professor there. The book is intense and I for one utilized other books and resources to build some bit of intuition for the material. His lectures are interesting until you realize he is going straight from the book and fails to explain and expand on crucial concepts in different meaningful ways. He does not break down the proofs enough for the class to have any "ah-ha" moments. He assumes competency in the proofs and consistently says, "Come on guys, you should know this" as a constant response to any sort of confusion the class may have. This is a graduate course and as such most students are Master/Phd students. If you are an undergraduate student, I would not take this course unless you are solid with rigorous proofs and have a solid mathematical intuition. Also, CS Theory is the pre-req course but it is a joke and very trivial compared to this course. There is a huge leap from messing around with Turing Machines in the first couple chapters of Sipser than jumping to Barak's material trying to fathom the complexity zoo. The TAs were okay. Their grading was intense…

Though I have taken statistics and probability courses in the past, this course did a great job introducing me to new probability tools that are especially relevant to theoretical computer science. After defining basic information theory concepts, we applied them to the study of communication complexity, algorithm lower bounds, interactive compression, and data structures problems. The class convinced me that information theory is the "right" language to describe probability in computer science. In terms of instruction, Omri did a pretty good job. He provided intuition for each definition and proof. However, I feel like he spent a little too long on introductory material; given this was a 6000-level class, I think most of the students would have been fine skipping a good chunk of introductory material, and we could have covered more.

Homeworks are straightforwards (can easily get 95+, but the averages were low) Midterm was very easy Final was harder but pretty doable with a complete understanding of the material

The reviewer below clearly has not taken any advanced math class at Columbia. Omri's explanations of theoretical concepts is very good, and if you have any experience with proof based math courses, you will probably really enjoy his exposition. The reviewer is correct that lectures are the exact same as the textbook, but that doesnt mean that they are not worth going to; reading and understanding the textbook by yourself can take an extremely long time whereas Omri will streamline and highlight important parts of the proofs in class.

1 problem set every roughly three weeks, which is reasonable. They can take a while to do, however, if you do not understand the material. Midterm was very straight forward and the class average was like 94%, but the final was atrocious. The average is not released at this time of writing but it is probably around 40%.

Definitely not the best at explaining concepts, which is kind of critical considering that this course is very abstract and theoretical. It can also get very hard to take notes on his lecture because he often would not write down a complex idea he is talking about and/or scribble very few words about it. He does regurgitate the textbook almost verbatim, so you can totally get away with not attending class.