Mani Soma, A prof at UW, IEEE fellow
Read his Biosketch...:)
Wednesday, October 14, 2009
Monday, October 5, 2009
Jeff Erickson's list on "what a theorectical computer science student should know"
Things happened Last week included Mihai Pătraşcu's (yes, it was him again!) this contraversial blog post with 74+ comparably interesting comments! I highly recommend you to follow it a bit if you haven't done so.
I would like to quote today a comment by Jeff Erickson on related post.
It is a (a suprisingly long and diverse) list on "what he thinks a phd in theorectical computer science should know". Erickson is a computational geometrist. That is why his list contains a few of geometry results (or algebraic results that is useful in algebraic geometry?) that I never heard of, like persistent homology, de Casteljau's algorithm...But other than that , i think it is quite fair list. Check how many you haven't heard of and wiki them! :)
here is Erickson's (I think it is him) comment on this post "core TCS" (by Michael Mitzenmacher):
"I'm sure my answer will be horribly biased, but at the very least, it should touch on Voronoi diagrams, Van Emde Boas trees, the dynamic optimality conjecture, Vapnik-Chernovenkis dimension, the Immerman–Szelepcsényi theorem, the Lovasz Local Lemma, spectral partitioning, Bloom filters, boosting, Arrow’s paradox, Nash equilibria, Azuma's inequality, zero-knowledge proofs, the PCP theorem, smoothed analysis, coresets, Reed-Solomon codes, distributed cache consistency protocols, interior-point methods, persistent homology, AKS sorting networks, monadic second-order logic, snake sort, evasive graph properties, the Okamura-Seymour theorem, natural proofs, Ramsey theory, fractional cascading, communication complexity, doubling dimension, derandomization, soft heaps, the power of two choices, the Graph Minor Theorem, Krylov subspace iteration, Euclid's algorithm, Dijkstra's algorithm, Boruvka's algorithm, Dehn's algorithm, Grover's algorithm, Buchberger's algorithm, de Casteljau's algorithm, Khachiyan's algorithm, Bresenham's algorithm, Dinits's algorithm, Lloyd's algorithm, and how to quickly look up lots of impressive-sounding results on Wikipedia."
I would like to add a few things I really like and think are equally important/elegent:
Dynamic programming speedup and SMAWK algorithm, expander, Karp-Luby and Karp-Luby-Madras , Alon-Matias-Szegedy algorithm, regularity lemma, perfect graph theorems, treewidth, Baker's shifting technique, Digital fountain, Lovasz's Sandwich theorem... I can only recall this many at this point and probably will update it later.
Also I would like to see a similar list for DB students. Hellerstein and Stonebraker 's list might be a good starting point.
I would like to quote today a comment by Jeff Erickson on related post.
It is a (a suprisingly long and diverse) list on "what he thinks a phd in theorectical computer science should know". Erickson is a computational geometrist. That is why his list contains a few of geometry results (or algebraic results that is useful in algebraic geometry?) that I never heard of, like persistent homology, de Casteljau's algorithm...But other than that , i think it is quite fair list. Check how many you haven't heard of and wiki them! :)
here is Erickson's (I think it is him) comment on this post "core TCS" (by Michael Mitzenmacher):
"I'm sure my answer will be horribly biased, but at the very least, it should touch on Voronoi diagrams, Van Emde Boas trees, the dynamic optimality conjecture, Vapnik-Chernovenkis dimension, the Immerman–Szelepcsényi theorem, the Lovasz Local Lemma, spectral partitioning, Bloom filters, boosting, Arrow’s paradox, Nash equilibria, Azuma's inequality, zero-knowledge proofs, the PCP theorem, smoothed analysis, coresets, Reed-Solomon codes, distributed cache consistency protocols, interior-point methods, persistent homology, AKS sorting networks, monadic second-order logic, snake sort, evasive graph properties, the Okamura-Seymour theorem, natural proofs, Ramsey theory, fractional cascading, communication complexity, doubling dimension, derandomization, soft heaps, the power of two choices, the Graph Minor Theorem, Krylov subspace iteration, Euclid's algorithm, Dijkstra's algorithm, Boruvka's algorithm, Dehn's algorithm, Grover's algorithm, Buchberger's algorithm, de Casteljau's algorithm, Khachiyan's algorithm, Bresenham's algorithm, Dinits's algorithm, Lloyd's algorithm, and how to quickly look up lots of impressive-sounding results on Wikipedia."
I would like to add a few things I really like and think are equally important/elegent:
Dynamic programming speedup and SMAWK algorithm, expander, Karp-Luby and Karp-Luby-Madras , Alon-Matias-Szegedy algorithm, regularity lemma, perfect graph theorems, treewidth, Baker's shifting technique, Digital fountain, Lovasz's Sandwich theorem... I can only recall this many at this point and probably will update it later.
Also I would like to see a similar list for DB students. Hellerstein and Stonebraker 's list might be a good starting point.
Subscribe to:
Posts (Atom)
