Computational Complexity Geomblog
geomblog.blogspot.com · Personal blog · on HN since 2009
Suresh Venkatasubramanian, a computer scientist, writes about algorithms, theory, data models, and academic and professional computing communities.
What HN saysHN commenters link it for the crowdsourced review of the Deolalikar P vs NP proof, which one calls amazing, and for theory discussions.
15HN people shared it
2linked it in comments
16stories submitted
78story points
12 years agolast shared
2009people per year2026
Most-shared posts
- 1Bob Morris and stream algorithms2 people · 10 points · first shared 2011 · discussion on HN
- 2Soviet-style mathematics1 people · 26 points · first shared 2009 · 5 comments on HN
- 3A response to Vint Cerf on how the ACM can do more for professional programmers1 people · 15 points · first shared 2014 · 7 comments on HN
- 4Deep Learning and the evolution of data models1 people · 6 points · first shared 2012 · discussion on HN
- 5Algorithms is the new Algorithms1 people · 4 points · first shared 2014 · discussion on HN
- 6Correlation Clustering: I don't like you, but I like them...1 people · 3 points · first shared 2009 · discussion on HN
- 7Optimal Distributed Sampling1 people · 3 points · first shared 2012 · discussion on HN
- 8Bad Research as Spam1 people · 2 points · first shared 2010 · 1 comments on HN
- 9Theory "vs" Practice1 people · 2 points · first shared 2009 · discussion on HN
- 10Picking a random element from a stream1 people · 2 points · first shared 2011 · 1 comments on HN
- 11Data Mining, machine learning and statistics1 people · 1 points · first shared 2014 · discussion on HN
- 12Could the IPad make computer science obsolete?1 people · 1 points · first shared 2010 · 1 comments on HN
- 13On reverse engineering algorithms and invisible choices that add research value1 people · 1 points · first shared 2014 · discussion on HN
- 14Distributed Learning: A new model1 people · 1 points · first shared 2013 · discussion on HN
- 15The 5+5 Commandments of a Ph.D.1 people · 1 points · first shared 2011 · discussion on HN
What HN people wrote when they linked it
Jun8 · 2010-08-10
Precisely! I found the crowdsourcing approach that got started at http://geomblog.blogspot.com/2010/08/on-deolalikar-proof-crowdsourcing… amazing. Terence Tao had done a similar thing, not for paper review but to prove some theorems.
Compared to this, the rigid approach adopted in Math Overflow to close any discussion on the issue seems so 19th century. See the discussion here: http://meta.mathoverflow.net/discussion/590/
rivalis · 2012-12-15
I am a graduate student at a big state university, studying complexity theory. I TA for the (required) introduction to discrete mathematics sometimes, and when we study FSM's I get to have a lot of fun motivating them for the students.
Automata theory may seem arcane, but if you want to truly understand concurrent programming, protocol design, robust systems, etc, you need good cognitive models. Heck, Erlang (one of my favorite languages for massively distributed computing) has some nice OTP stuff (http://www.erlang.org/documentation/doc-4.8.2/doc/design_principles/fs… built in for using FSMs to make your code sane and robust.
FSM's are one of the theoretical CS concepts that it is easiest to see the practical use for, but other TCS tends to be just as useful if you look at it right. Eg, space complexity right? For the most part that doesn't matter, does it? Nope. A bunch of modern internet-sized problems end up being streaming problems (http://geomblog.blogspot.com/2005/05/streaming-algorithms.html), and you need to understand basic space complexity, linear algebra, and probability, all of which a good CS degree will get into your head. I think the role of a good CS degree is to get some theory into people's heads, so that they have the right cognitive models for tackling difficult problems that come up in the real world.
I'm not saying that a CS degree is necessary to be a good programmer, or that you can't pick up those mental tools without a CS degree if you…