Tal is wicked smart, evident from day 1, and is super knowledgable about the subject. Unfortunately, I think this somewhat hinders her from succinctly explaining the concepts to half the class just because we're too dumb to understand it (at first at least). Another issue that I found out in the second half of the term is that I was getting too caught up in the fine details of what was being taught in the lecture and wasn't really getting a full picture. But taking a step back from the material to see the larger picture, especially during the Turing Machine section, helped immensely. Even though I struggled with just about everything in the course, I would recommend taking it with Tal because she is super intelligent and is really helpful and approachable in office hours. I only went to her office hours towards the end of the class because I thought she would be somewhat intimidating but this was not the case at all. Some, myself included, found her intimidating in class because she would sometimes answer student's questions with "I'm not sure where your getting confused" which can be awkward for the student asking the question but Tal doesn't mean it with an ill intention. So, if you can get over this bit you should be fine or go to her OH and ask in a smaller setting. I'm not sure how this course will be structured when we go back to campus but the format was three unit tests worth 30%, 30%, 10% of your final grade. I got somewhat below average on all of them - nothing by more than 5% less than average - but did fine on the homework (except for one where I got 50! lol) and the quizzes and ended up with a B+ so the curve is really generous. For context, the averages for the tests in fall 2020 were around 70% each time and I genuinely thought I had failed the second test which was worth 30% yike. With all that being said, I do think that the homework grading can be inconsistent and sometimes (rare for me at least though) just doesn't make sense. Grading is not always inconsistent, but it certainly feels shitty when something unfortunate like that happens to you. But, as long as you go to office hours when confused you should be able to get some helpful pointers about where to start - some TAs are more helpful than others so best to figure that out in the beginning of the term. This class was one of those courses where I disliked it during the course but reflecting on it, it wasn't so bad. That is a strong argument for not taking the course though... TLDR: The curve will save you even if you feel like you are failing.
I used to aim for A/A- for all of my classes, but I think I'm failing this course.
It’s the inconsistent grading and severe penalties to the point that it'd be better to not even try on exams/homework sometimes. I would get 0 points for a proof on one part of a problem but then get credit for the same proof on the next part of the same problem graded by another TA. The professor did not make the class enjoyable for us but it was mostly the TAs that made the class difficult. Unless you have to take this for computer science, do yourself a favor and do not suffer through this. Could not be more thankful for pass/fail.
Professor Malkin is absolutely incredible. She teaches concepts clearly in class and responds to Piazza posts quickly and with in-depth, thorough answers. Literally, I've never taken a class in which the Professor responds on Piazza even more often than the TAs do (and at odd hours of the night, too!). She is a fantastic lecturer and makes the course material super super interesting-- and I say that as someone who has never been interested in the theoretical underpinnings of CS. I would highly recommend taking this class with her.
I highly disagree with the recent reviewer of Fall 2020. This class is required for CS majors only take if you have to or you like the material. The quizzes take at least 30 minutes-1 hour even if you've gone to all lectures. She assigned homework due 1 day before an exam and it was over the break (with no office hours then). She seems out of touch with the students. She judges people's questions in class. Last lecture she spent the entire class (except the last 15 minutes) going over the previous quiz... She manages time poorly. At least now she knows how to work Zoom (the first few weeks/into midterms she had problems with Zoom where class would not start until 20-30 minutes later). She often omits proofs. Oh and she combined her 8:40am and 10:10am sections, so she only teaches 2x per week, and if you have a conflict with the other class time (because you signed up for a specific time of this class) you're forced to watch the recordings and not attend live.
The worst professor I have ever had. Tal doesn't actually teach and her class is not formatted for virtual learning. Why does she omit every proof and tells us to "think at home" when we are all very clearly already at home? The world may never know. I've learned nothing in this class. And frankly, I'm confused as to how she has a silver nugget because that is the biggest joke of 2020.
I highly recommend taking this course with Professor Malkin! Prof Malkin is extremely intelligent and this is clear in the way she presents her lectures. She is clear, concise and really makes the subject matter easy to understand. She covers all bases and encourages you to think in non traditional ways. She is also approachable and always answers questions.
A well-executed class. Tal Malkin is very clear, puts a lot of effort into teaching, and knows that mathematical maturity among her audience varies wildly. Thus, she gives intuition as well as rigor, followed by many examples. She likes to get people to participate in lecture by answering or asking questions. This can be either illuminating or frustrating, depending on said people in class. For the most part, lectures followed Sipser quite closely, although she merely sketched many of the more involved proofs, e.g. for PCP. The material was interesting enough, and she tries to give some motivation or application. However, the complexity portion of the class was much too rushed: we skipped many proofs and handwaved everything else. Recitation notes were regularly posted, and these were quite long and poorly LaTeXed but very thorough, so I can't complain. Most everybody who takes this class has to, so I recommend taking her iteration of it.
What a fun course! Each lecture, professor Malkin presented an overview of a recent cryptography result. Very interesting without getting caught up in tedious details. Here [http://www.cs.columbia.edu/~tal/6261/SP16/] is an overview of the topics she did this semester, although it changes from class to class. Lecture was only a small part of the class. The main event the project. The goal was to read up on an area of cryptography, discuss an open problem, then attempt to do original research in it. Professor Malkin was very helpful in the process, and she put a lot of time into helping groups find papers and work on results. It presented a glimpse into what crypto research is like. Everyone presented their work on the last day of class. This class assumes a background in cryptography and theoretical computer science. You should be comfortable with proofs, especially the proofs of security used in cryptography.
Prof. Malkin is the best. Not only does she understand and explain the material very thoroughly, she also makes a genuine effort to learn her students' names and engage the class. She has this one-liner which she uses when nobody raises their hand: "You either do not understand and should ask a question, or you understand and can give me the answer." - Prof Malkin's honesty/authenticity shows through in one-liners like this one. Lecturing style - probably one of the best lecturers in the department. She does this thing where she gives a hand-waving, intuitive explanation of something, and then shows it formally. She is extremely approachable and very open about how grading is done in the class. Prof. Malkin and her TAs put in an try very hard to make the course fair, always retroactively applying a policy change to all students if one student brings it up, and I think that this attitude starts at the top with Prof. Malkin setting the example.
A pretty good class. Prof. Malkin makes a point of offering both conceptual and formal treatments of the material, which in principle is nice (as just about every result in crypto is deeply counterintuitive); in practice, I found her lemma-proof-theorem teaching very clear, but the high-level explanations so vague as to be practically useless. Part of the issue was that a large portion of the class didn't really have the mathematical maturity necessary for this course, and she would get bogged down answering basic questions and then have to rush through material. She got better at this (i.e. stopped answering stupid questions) as the semester went on, but it remained frustrating throughout. Homework assignments were well-designed. Fernando (the TA) was a real stickler for rigor, and I definitely learned to be more careful about writing up proofs by the end of the semester. Midterm (in class) and final (take home) were both trivial; I don't know what the final average was, but due to the aforementioned mathematical maturity problem midterm scores were shockingly low. As a side note, this can be a great class even if you're not specifically interested in security. I was in learning theory at the same time, and my final project for that class relied on a bunch of cryptographic hardness assumptions---this is about a lot more than secret codes.
Potentially a very dry topic, but Prof. Malkin was able to make it interesting. Mostly because she seems to believe a great deal in class participation, and engaged students in every derivation. Overall, I'd rate her highly.
Hell if I know. I never went. The website says "CS Theory is the last course required of all CS undergrads", but it should probably be more like "CS theory is the last course of the day, don't bother." The topics mostly overlap with other courses (data structures) -- if you stay at home and read up on regexps and such, you'll be completely fine. The homeworks are basically perfect reflections of what you're accountable for, so if you can do them you're set. I'm not really complaining about Tal, she's pretty OK. At the end of the day, it's just another CS course repeating the same damn curriculum.
Prof Malkin is very approachable and is definitely on your side - but she won't go find you, you have to send her e-mails and especially go to her office hours. Her lectures are thorough and cover the book material pretty strictly, but I think she'd be more helpful if she spent a little more time structuring the material, saying "You are here" in the grand scheme of Computation and it's Proofs. Indeed, I think a map could be drawn of the proofs and their relationship to one another - this would help a lot in understanding the dependencies of proofs upon each other. Whatever you do READ AHEAD OF THE LECTURE. This stuff is nearly impossible to simply hear and absorb in clas, so having thought about the concepts beforehand will make all the difference in the world. Hell, you might even enjoy it.
If you don't your remember probablity and other math from Algorithms then don't bother taking this class because you'll get killed. In other words, don't ignore the prerequisties for the class because the Prof. will assume that you're comfortable with all the concepts that she listed on the class website. Her lectures are not that good and neither is her handwriting. Fortunately, she makes everybody participate in this thing where in each lecture a student is chosen to take notes for the class. The student is then responsible for converting the notes into LaTeX or PDF and share it with the rest of the class. There are 6 homeworks and one final exam. The homeworks are pretty long so start early. They'll require you to do some mathematical proofs, encryption scheme design, and other theoretical stuff. Take this class only if you're really interested in Cryptography.
This course is definitely a heavy theory course. The lectures were fairly long, but definitely well done; Professor Malkin is an excellent lecturer. She doesn't use PowerPoint, which I personally consider a plus, though it means that you can't skip lectures if you expect to learn something from them.
Prof. Malkin is one of the is the best professors I have had in the CS department. She's brilliant, but can explain topics clearly and doesn't make you feel like a moron. Go to class because the homework and test questions are based on her lectures. She's very friendly and approachable. However, don't even try to BS her. She will not give out last minute extensions (unless you have an emergency) and collects homework at the beginning of class or it's considered late. Take the time and do the problem sets yourself. This is one of those classes where you cannot cram the night before the test and expect to do well. You have to really understand the concepts.
Great professor who really, really knows her stuff. Lectures well and does not use slides (as Grunschlag does) so going to class is important. Friendly and helpful during office hours. Funny and very likable! Subject material itself is very interesting and creative, but can also confuse and/or frustrate (especially people who are not very mathematical) because it is all proofs and the problems are extremely interrelated and similar. Reading ahead a bit before lecture would definitely help tremendously.