COMS W4236

4 assignments throughout the semester, takes about 10-20 hours, a pretty straightforward midterm, and a really difficult final

4 PSETs that are each 15% of the grade Midterm and Final are each 20% and they are take-home. The PSETs were incredibly time consuming, taking upwards of 20 hours each. You have to start them in advance

HWs take a lot of thinking but there are also only 4 of them. It's not a hard class if you are willing to put in the time. 60% HW + 20% Midterm + 20% Final. Exams all take-home. Time commitment hard to estimate: most of the problems are either you get it or you dont. I was stuck on this one question for a couple of days and that's all I did for those days, so, hard to say.

problem set every 2 weeks, midterm, final.

A very well organized and delivered class, teaches you the foundations of complexity theory and enables you to dive deeper into complexity theory on your own if you want to. All lectures closely follow some textbooks/online notes which makes it way easier to follow along. The class materials can get really challenging sometimes, but with the notes it is very possible to get a good grasp of it as long as you put in the time. Prof is approachable, patient, and explains things well.

Would highly recommend taking a class with Henry if you have the chance. I took computational complexity with him, not quantum computing, which his research focuses on, and he was amazing. The class is very difficult in terms of content but it is also incredibly rewarding and interesting. If you are tired of 300 person lectures this class is perfect. Henry and the TAs were very approachable and helpful in office hours. If you attend lecture and office hours I think the PSETS are doable if you don't start them last minute. They are also spread out so that you have sufficient time to complete.

I'm much more luke-warm about our man. He's find, but I wouldn't go out of my way to say that he's the best. The biggest problem of his class is that he's too accommodating as in that his class is quite easy, compared to what you can find online, proved by the medians of the last couple assignments being 86.5-87. Another thing is that the TCS department at Columbia is no-kidding the best STEM department at Columbia, so, in comparison, I just can't say that Rocco is the best prof I've had. But, compared to any other department, yea, he is very very good, hands down.

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…

Pretty good course, considering you enjoy this material. His lectures are pretty good and material is presented in an interesting way. Some of the homework problems are pretty difficult, but doable. Grading is pretty good too. The only complaint is don't expect too much help outside the classroom. He pretty much ignores questions sent to him and doesn't seem to care too much outside the classroom.

The problem sets for this class were very challenging and sometimes took 5-20 hours to complete. This number varies wildly because the point of the hard problems in the set is to come up with an idea for an algorithm (or a hardness proof showing that there cannot exist an efficient algorithm), and the time this takes depends on how long you have to brainstorm until you think up the key ideas. The midterm was too easy. The final was extremely challenging.