Communications of the ACM
Refine your search:
How the “Frontier” Became the Slogan of Uncontrolled AI
Artificial intelligence (AI) has been billed as the next frontier of humanity: the newly available expanse whose exploration …
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...
From Computational Complexity
50 Years of the Turing Award
The ACM knows how to throw a party, a two-day celebration of the 50th anniversary of the Turing Award. Every recipient got a deck of Turing Award playing cards...
From Computational Complexity
Best. STOC. Ever.
The Panel on TCS: The Next Decade Last week I attended STOC as its first new TheoryFest in Montreal. Pretty much everything about TheoryFest went extremely...
From Computational Complexity
Joan Clarke (1917-1996)
I'm in San Francisco for the ACM conference celebrating 50 years of the Turing Award. I'll post on STOC and the Turing award celebration next week. Today though...
From Computational Complexity
The Power of Economic Inefficiency
I grew up in a time when long distance domestic phone calls from AT&T costed $0.20/minute off peak ($1.30 in today's dollars). I also grew up close to AT&T Bell...
From Computational Complexity
Theory Jobs 2017
In the fall we point to theory jobs, in the spring we see who got them. Like last year and years past I created a fully editable Google Spreadsheet to crowd source...
From Computational Complexity
Who Sets Policy?
In April the New York Times Magazine ran an article Is it O.K. to Tinker with the Environment to Fight Climate Change? The article asks about the ethics of even...
From Computational Complexity
Graduation from the Other Side
I've attended many graduations in my time, mostly as faculty, a couple of times as a student or a brother. This last weekend I attended my first university...
From Computational Complexity
The Optimizers
Last week the Georgia Tech School of Industrial and Systems Engineering honored the 80th birthday of George Nemhauser and the 70th of Arkadi Nemirovski at an...
From Computational Complexity