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
Favorite Theorems: Algebraic Circuits
Most of my favorite theorems tell us something new about the world of complexity. But let's not forget the greatest technical challenges in our area: proving separations...
From Computational Complexity
The Godzilla Moment
On the plane earlier this week I got around to watching the Academy Award winning movie Godzilla Minus One, one of the best monster movies I've seen set in Japan...
From Computational Complexity
Double Digit Delights
It started with a post from Fermat's Library. 132 is the sum of all the 2-digit numbers made from its digits. It is the smallest such number. pic.twitter.com/hrByAXbr51...
From Computational Complexity
Peer Review
Daniel Lemire wrote a blog post Peer Review is Not the Gold Standard in Science. I wonder who was claiming it was. There is whole section of an online Responsible...
From Computational Complexity
Jim Simons (1938-2024)
Jim Simons passed away Friday at the age of 86. In short he was a math professor who quit to use math to make money before it was fashionable and used part of his...
From Computational Complexity
Favorite Theorems: Dichotomy
A constraint satisfaction problem has a group of constraints applied to a set of variables and we want to know if there is a setting of the variables that makeA...
From Computational Complexity
Our Obsession with Proofs
Bullinger's post on this blog last week focused on Vijay Vazirani's public obsession of finding a proof for the 1980 Micali-Vazirani matching algorithm. But why...
From Computational Complexity
Is Persistence an Anachronism?
Guest post by Martin BullingerVery recently, Vijay Vazirani's paper A Theory of Alternating Paths and Blossoms, from the Perspective of Minimum Length got accepted...
From Computational Complexity
Favorite Theorems: Quantum Provers
For our next favorite theorem, we look at the surprising power of provers who share entangled bits. If you can prove something to an arbitrarily computable verifier...
From Computational Complexity