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
MohammadTaghi HajiAghayi on David Johnson
More than a week ago, I heard the very sad news that David Johnson has passed away after one year fight with cancer. I felt that I should write a memorial note...
From Computational Complexity
Complexity versus Complexity
For those interested, I've started writing posts for the Predictwise Blog. Predictwise makes predictions of future events such as who will win the Republican Nomination...
From Computational Complexity
The Value of Shapley
Nobel laureate Lloyd Shapley passed away Saturday. We best know Shapley for his stable matching algorithm with David Gale. Nicole Immorlica guest posted on stable...
From Computational Complexity
David Johnson (1945-2016)
David Johnson, a leader and advocate for algorithms and all of theoretical computer science, passed away last night at the age of 70. A truly sad day for us all...
From Computational Complexity
Changing This Ancient Art Into a Science
The ACM announced yesterday that they will award the 2015 Turing Award to Whitfield Diffie and Martin Hellman for contributions to modern cryptography. The Turing...
From Computational Complexity
Primary Game Theory
[Nominations open for the SIGACT Distinguished Service Prize. Deadline: April 1] The US presidential primaries have not gone as expected as you can see from the...
From Computational Complexity
Posting Papers
In the ancient days of the 80's, if someone wanted a paper from you, they would ask and you would mail via post. Sometimes I would get a self-addressed envelope...
From Computational Complexity
The Moral Hazard of Avoiding Complexity Assumptions
Moshe Vardi's CACM editor letter The Moral Hazard of Complexity-Theoretic Assumptions practically begs a response from this blog. I also encourage you to read the...
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