professor


Jan 2020 
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.
Jan 2020 
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.
Dec 2019 
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.
Jan 2019 
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 "ahha" 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 prereq 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 and they expected a lot from the students. Do not take this course if you think it will be an easy grade. I would take this course with Xi Chen or even Rocco who seem to dive deeper into the specific nuances of each proof. TLDR: Only take this course if you need it or are stellar in mathematical proofs, they will not hold your hand. Take with other professors for more in depth explanations of material.
Jan 2018 
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 6000level class, I think most of the students would have been fine skipping a good chunk of introductory material, and we could have covered more.