4 ms·

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 do

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.ProbMethod3ed.pdf 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 https://arxiv.org/abs/2309.09913

pushedx 3y ago
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-s09/Site/Calendar/calendar.html 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.
- soganess 3y ago
  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-sp20/ 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.
  - pushedx 3y ago
    Ah, great! Seems like there was a tradition of having fun with the course title.
dogcomplex 3y ago
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.
- Karrot_Kream 3y ago
  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".
  - dogcomplex 3y ago
    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

pushedx 3y ago

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-s09/Site/Calendar/calendar.html 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.

soganess 3y ago
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-sp20/ 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.
- pushedx 3y ago
  Ah, great! Seems like there was a tradition of having fun with the course title.

dogcomplex 3y ago

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.

Karrot_Kream 3y ago
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".
- dogcomplex 3y ago
  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