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
Why Can't We Break Crytptography?
In the recent Signalgate scandal, several senior Trump administration appointees used the Signal app on their phones to discuss an attack on the Houthis. People...
From Computational Complexity
PDQ Shor (?-2025)
PDQ Shor PDQ Shor, Peter Shor's smarter brother, passed away last week. PDQ was a Physicist/Computer Scientist/Mathematician/Astrologer/Psychic at the University...
From Computational Complexity
What Happened to MOOCS?
In 2012 I wrote a blog post about the growing influence of Massively Open Online Courses, or MOOCs.John Hennessey, president of Stanford, gave the CRA keynote address...
From Computational Complexity
A Failure to Communicate
With care you can explain major ideas and results in computational complexity to the general public, like the P v NP problem, zero-knowledge proofs, the PCP theorem...
From Computational Complexity
Covid and Complexity
As we hit five years from when the world shut down, lots of discussions on how Covid has changed society. What about academia and computer science?It's a challenging...
From Computational Complexity
Taking a Stand
On February 20th we got the news from the National Science Foundation Algorithms Foundations Team that long-time NSF program director Tracy Kimbrel, was leaving...
From Computational Complexity
You Need Much Less Memory than Time
Just as I was complaining that we haven't seen many surprising breakthroughs in complexity recently, we get an earthquake of a result to start the year, showing...
From Computational Complexity
Tomorrow and Yesterday
I recently completed Tomorrow, and Tomorrow, and Tomorrow by Gabrielle Zevin, a book recommended by many including the City of Chicago. The novel covers the decades...
From Computational Complexity
Research Then and Now
A student asked me if complexity research was easier when I was a student. Interesting question. Let's compare research now versus the late 80's.The big advantage...
From Computational Complexity
The Situation at the NSF
The National Science Foundation is one of the agencies most affected by the various executive orders issued by the Trump administration. As a critical funder of...
From Computational Complexity
The NSF From the Inside
The National Science Foundation is one of the agencies most affected by the various executive orders issued by the Trump administration. As a critical funder of...
From Computational Complexity
Lautemann's Beautiful Proof
In writing the drunken theorem post, I realized I never wrote a post on Lautemann's amazing proof that BPP is contained in \(\Sigma^p_2\), the second level of the...
From Computational Complexity
The Fighting Temeraire
What does an 1838 painting tell us about technological change?A colleague and I decided to see how well LLMs could teach us a topic we knew nothing about. We picked...
From Computational Complexity
"Our Days Are Numbered"
Slide in Lev Reyzin's JMM talk "Problems in AI and ML for Mathematicians" Reyzin is paraphrasing Telgarsky. Posted with permission. Last week I attended the Joint...
From Computational Complexity
My Drunken Theorem
Bill's SIGACT Open Problems Column remembering Luca Trevisan is out. I chose the problem of whether Promise-ZPP in P implies Promise-BPP in P, an extension of an...
From Computational Complexity
Complexity Year in Review
Back in the day (circa 1989) we studied locally random reductions which would lead to all those exciting interactive proof results. Somehow locally random reductions...
From Computational Complexity
Information is Physical?
I've heard a few times recently the phrase "Information only exists in a physical state". It come from the quantum computing world where they claim quantum changes...
From Computational Complexity
It's Time to Stop Using Grades
We use grades to evaluate students and motivate them to learn. That works as long as grades remain a reasonably good measure of how well the student understands...
From Computational Complexity
Favorite Theorems: The Complete List
Now in one place all of my sixty favorite theorems from the six decades of computational complexity (1965-2024).2015-2024 Graph Isomorphism (Babai) Sensitivity...
From Computational Complexity