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
Go Google Go
In 2009 I posted about a surprising new approach that moved computer Go from programs that lose to beginners to where it could beat good amateurs. That approach...
From Computational Complexity
We Still Can't Beat Relativization
As we celebrate our successes in computational complexity here's a sobering fact: We have had no new non-relativizing techniques in the last 25 years. A little...
From Computational Complexity
The Growing Academic Divide
The decreases of the past three years bring the number of advertised jobs to a new low, below the level reached after the severe drop between 2007–08 and 2009...
From Computational Complexity
Rūsiņš Freivalds (1942-2016)
Rūsiņš Mārtiņš Freivalds passed away on Monday from a heart attack at the age of 73. I met Freivalds several times often through Carl Smith, who passed away himself...
From Computational Complexity
Complexity Year in Review 2015
We had an incredible year for theorems in 2015, the strongest year in computational complexity in the last decade. Topping the list as the theorem of the year is...
From Computational Complexity
Guns and Crypto
“We believe it would be wrong to weaken security for hundreds of millions of law-abiding customers so that it will also be weaker for the very few who pose a threat...
From Computational Complexity
Blog Followers
If you follow this or any other Blogger-based blog via a non-Google account, you'll need to follow with a Google account instead. Details.
From Computational Complexity
Simons and Berkeley
The Simons Institute for the Theory of Computing in Berkeley held two programs this fall, Fine-Grained Complexity and Algorithm Design and Economics and Computation...
From Computational Complexity
Ada Lovelace (1815-1852)
Back in my teens I had ordered my first computer, a TRS-80 from Radio Shack, and I grew anxious in the weeks before it arrived. I learned the basics of BASIC...
From Computational Complexity
Moonshots
In 1961 Kennedy said "this nation should commit itself to achieving the goal, before this decade is out, of landing a man on the Moon and returning him safely to...
From Computational Complexity
Star Trek Computing
In the wake of Leonard Nimoy's death last February, I decided to rewatch the entire original Star Trek series, all 79 episodes. I had watched them each many times...
From Computational Complexity
A Silly String Theorem
First a note on a serious theorem: Babai has posted a video (mp4, 1h 40 m, 653MB) of his first talk on his Graph Isomorphism algorithm. I was giving a talk on the...
From Computational Complexity
A Primer on Graph Isomorphism
I spent 14 years on the faculty at the University of Chicago. I know László Babai well, we collaborated on some of my best known work. I also know Ryerson 251...
From Computational Complexity
George Boole (1815-1864)
George Boole, the father of symbolic logic, was born two hundred years ago today. His 1854 treatise, An investigation into the Laws of Thought, on Which are founded...
From Computational Complexity
S. Barry Cooper (1943-2015)
Barry Cooper, a computability theorist and professor at the University of Leeds, passed away on Monday after a brief illness. Cooper was a big proponent of computability...
From Computational Complexity
Complexity Blast from the Past
My friend Marty in grad school mysteriously disappeared in 1985 and showed up yesterday looking exactly the same as I remember him. He said he traveled into my ...
From Computational Complexity
2015 Fall Jobs Post
When the 2014 fall jobs post is our most popular post, you know it is time for the 2015 jobs post. This year instead of (or in addition to) posting your jobs in...
From Computational Complexity
Randomness by Complexity
Let n be the following number 135066410865995223349603216278805969938881475605667027524485143851526510604859533833940287150571909441798207282164471551373680419703964191743046496589274256239341020864383202110372958725762358509643110564073501508187510676594629205563685529475213500852879416377328533906109750544334999811150056977236890927563 ...
From Computational Complexity
Cancer Sucks
Karsten Schwan said the title quote when we were gathered as a faculty two years ago mourning the Georgia Tech School of Computer Science faculty member Mary...
From Computational Complexity