Sign In

Communications of the ACM

Blogroll



From Computational Complexity

The Grad Student Tax

By now as you've read from Luca or Scott or PhD Comics or a variety of other sources on the dangerous changes to the tax code that passed the US House of Representatives...

From Computational Complexity

A Tale of Three Rankings

In the Spring of 2018 the US News and World Report should release their latest rankings of US graduate science programs including computer science. These are the...

From Computational Complexity

Advice for the Advisor

A soon-to-be professor asked me recently if I could share some ideas on on how to advise students. I started to write some notes only to realize that I had already...

From Computational Complexity

Matching and Complexity

Given a group of people, can you pair them up so that each pair are Facebook friends with each other? This is the famous perfect matching problem. The complexity...

From Computational Complexity

2017 Fall Jobs Post

You're finishing up grad school or a postdoc and ask yourself what should I do for the rest of my life? We can't answer that for you but we can help you figureCRA...

From Computational Complexity

The Amazon Gold Rush

Unless you have hidden under a rock, Amazon wants to build a second headquarters in or near a large North American city. Amazon put out a nice old fashioned...

From Computational Complexity

Lessons from the Nobel Prizes

We've had a big week of awards with the Nobel Prizes and the MacArthur "Genius" Fellows. The MacArthur Fellows include two computer scientists, Regina Barzilay and...

From Computational Complexity

Monty Hall (1921-2017) and His Problem

Monty Hall passed away yesterday, best known for co-creating and hosting the game show The Price is Right, a show I occasionally watched as a kid. To the best...

From Computational Complexity

Tragic Losses

I'd like to remember two young people who's lives were taken way too early. I didn't know either well but both played large roles in two different communities...

From Computational Complexity

Random Storm Thoughts

It's Monday as I write this post from home. Atlanta, for the first time ever, is in a tropical storm warning. Georgia Tech is closed today and tomorrow. I'm just...

From Computational Complexity

Rules and Exceptions

As a mathematician nothing grates me more than the expression "The exception that proves the rule". Either we bake the exception into the rule (all primes are odd...

From Computational Complexity

NOT So Powerful

A monotone circuit has only AND and OR gates, no NOT gates. Monotone circuits can only produce monotone functions like clique or perfect matching, where addingFavorite...

From Computational Complexity

Kurtz-Fest

Stuart Kurtz turned 60 last October and his former students John Rogers and Stephen Fenner organized a celebration in his honor earlier this week at Fenner's...

From Computational Complexity

The Crystal Blogaversity

A joint post from Lance and Bill This blog started fifteen years ago today as  "My Computational Complexity Web Log". Bill came on permanently in 2007 after Lance...

From Computational Complexity

The World is Not for Me

I wanted to address diversity after the Google memo controversy but that shouldn't come from an old white man. I asked my daughter Molly, a college student trying...

From Computational Complexity

Wearable Tech and Attention

Remember the Bluetooth craze where it seemed half of all people walked around with a headset in their ear. Now you rarely do. Remember Google Glass. That didn't...

From Computational Complexity

What Makes a Great Definition

Too often we see bad definitions, a convoluted mess carefully crafted to make a theorem true. A student asked me though what makes for a great definition in theoretical...

From Computational Complexity

Peter Wegner (1932-2017)

Peter Wegner passed away yesterday morning at the age of 84. As a child he escaped Stalinist Russia and Nazi-occupied Austria the latter via the Kindertransport...

From Computational Complexity

Lessons from Norway

For the last two weeks, the wife and I took a vacation to beautiful Norway to see the fjords and the North Cape, effectively the northernmost point in Europe. It...

From Computational Complexity

The Complexity of Rubik's Cube

In my book I use Rubik's Cube as an example of a puzzle we can computationally solve efficiently (as opposed to Sudoku or Rush Hour). How does this square with...
Sign In for Full Access
» Forgot Password? » Create an ACM Web Account