Tag Archives: Theory Blogs

Best of the Year

I didn’t make any best-of-the-year lists, but I support the idea. I also support new year’s resolutions, but I’m not going to write about mine.

But the internet picks up the slack.

FlowingData has a 5 Best Data Vis of the year list, which I’m fond of. It includes the beautiful Streamgraphs of Byron and Wattenberg. Their technical report has some fun applications of combinatorial optimization to aesthetics.

Streamgraph at the box office

Lance Fortnow has a nice Complexity Year in Review on the Computational Complexity Blog. Unfortunately, I don’t have a beautiful illustration of Prasad’s result that Unique Games Conjecture implies semidefinite relaxations have optimal approximation ratios.

3 Comments

Filed under combinatorial optimization, general, TCS

Theory in Wikipedia

wikiScott Aaronson’s recent blog post about improving the state of computer science articles in Wikipedia has been generating some buzz this week. I’m happy to buzz along. Yay for Wikipedia!

Here are my top picks from Scott’s wishlist for the motivated encyclopedia writer:

  • Sketching algorithms
  • Streaming algorithms
  • Sparsest cut
  • Metric Embedding
  • Glauber dynamics
  • Average case complexity
  • Conductance (probability)
  • Max-flow min-cut

Frequent Wikipedia contributor David Eppstein also has his own todo list that you can draw inspiration from.

Comments Off

Filed under TCS