Hacker News Reader

Comment by soganess | Hacker News Reader

I don't know where, but there is another version of this class that includes "The Probabilistic Method"[1]. While not exactly the same thing, I can't imagine doing modern existential (vs constructive) proofs of topological solution space obstructions without that style of thinking.

[1]: https://math.bme.hu/~gabor/oktatas/SztoM/AlonSpencer.ProbMet...

Bonus points for those interested -- I think this paper(sadly, not mine) has a concise collection / history of obstruction proofs in its background section (1.2/1.3 and since it is a paper all of them are cited!): https://arxiv.org/abs/2309.09913

View on HN

You may be referring to the version of this course that was taught by Luis von Ahn (the creator of reCAPTCHA and the founder of Duo Lingo), when he was a professor at CMU.

https://www.cs.cmu.edu/afs/cs.cmu.edu/academic/class/15251-s...

He liked to call the course "SOME Theoretical Ideas FOR Computer Science", and it was known to be a very popular (and difficult) course.

I didn't know LVA taught at CMU, rad!

I did some digging and found the class: https://people.eecs.berkeley.edu/~venkatg/teaching/15252-sp2...

I enjoy that it is called "More Great Ideas in Theoretical Computer Science", like a sequel (...and 'some' being the prequel). I'm now eagerly awaiting the 'return of the jedi' installment.

Ah, great! Seems like there was a tradition of having fun with the course title.

Damn. Impressed to see something this fundamental that never made it into my computer science postgrad education (and judging by the depths and difficulty of it, might not for a while!) Seems like a powerful technique that scales to cover quite a lot of other problems.

Wow I'm really surprised this didn't enter your post grad! We covered this briefly in undergrad but had a much meatier grad level course on fundamentals of computational with this included and it destroyed pretty much every student in the class lol. Our professor ended the final at 4 hours to "spare you the misery".

hahaha okay actually in retrospect/closer inspection, I do think some teachers tried to instill these probability proofs from a different angle - though obviously it did not stick long past the testing, and I never thought of it as a fundamental new approach. Would definitely need to reformulate all of this into much more intuitive / visual metaphors to get it to really stick these days. Oddly I do a lot of thinking on the general fundamentals course content these days (FSAs, Turing Machines, etc) but I should really try to incorporate this probabilistic view

Reply on news.ycombinator.com