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
QED
Via Scott, John Horgan wrote a blog post following on his 1993 Scientific American article The Death of Proof. The article talked about computer-generated proofs...
From Computational Complexity
Flying Pigs Unsafe at Any Speed
Take a moment and imagine a flying pig. Do you see a pig with tiny wings lazily guiding along. But pigs are not particularly slow animals as anyone has seen a pig...
From Computational Complexity
Extra! Extra! Read all about it!
Last weekend I saw the documentary Joseph Pulitzer: Voice of the People. Pulitzer, as you probably know from the prize named after him, was a major newspaper publisher...
From Computational Complexity
The iPhonification of Everything
So you've got an iPhone XS in Space Grey. Congrats, so do 20 million other people. Maybe you have different cases but otherwise the hardware in all these phones...
From Computational Complexity
An Immerman-Szelepcsényi Story
As a grad student in the late 80's I had the opportunity to witness many great and often surprising theorems in computational complexity. Let me tell you aboutnondeterministic...
From Computational Complexity
Phish Before Turkey
The Chronicle of Higher Education recently published a story Phishing Scheme Targets Professors’ Desire to Please Their Deans — All for $500 in Gift Cards. TheFrom...
From Computational Complexity
Machine Learning and Wind Turbines
My daughter Molly spent six weeks on an environmental program in China last summer. When she got back she had to do a report on machine learning and wind turbines...
From Computational Complexity
The Cost of Privacy
Billboard at 2019 CES Computer scientists tend to obsess about privacy and we've had a privacy/security debate for decades now. But now machine learning has...
From Computational Complexity
Search versus Decision
Shockingly I've never done a post on search versus decision, one of the more interesting dualities in complexity. In short: Decision: Is there a needle in the haystack...
From Computational Complexity
Complexity Year in Review 2018
Result of the year goes to Oracle Separation of BQP and PH by Ran Raz and Avishay Tal which we wrote about in June. This work solves one of the original openQuanta...
From Computational Complexity
Ker-I Ko (1950-2018)
A few weeks ago as Bill and I prepared for our upcoming year in review post, we noted that we hadn't lost any theoretical computer scientists this year, at least...
From Computational Complexity
Inverting Onto Functions
Here's an open question that goes back to a 2003 paper that I wrote with Steve Fenner, John Rogers and Ashish Naik. The conference paper goes back to 1996. In...
From Computational Complexity
Remembering George H. W. Bush
Today is the national day of mourning for George Herbert Walker Bush, one of the best presidents for science and computing. He created PCAST, the President's...
From Computational Complexity
LOGCFL Venkat Style
H. Venkateswaran, a much loved professor in the School of Computer Science at Georgia Tech and a fellow computational complexity theorist, is retiring at the end...
From Computational Complexity
Simons and Amazon
I'm spending this week at the Simons Institute in smokey Berkeley, California. This fall Simons has a program in Lower Bounds in Computational Complexity. Scroll...
From Computational Complexity
The Data Transformation of Universities
With all the news about elections, caravans, shootings and attorney generals, maybe you missed the various stories about real transformations at our top universities...
From Computational Complexity
P = NP Need Not Give a SAT Algorithm
In Bill's post earlier this week, he asks if there is a fixed algorithm such that if P = NP, this algorithm will correctly compute satisfiability on all inputs....
From Computational Complexity
Good Results Made Meaningless
Sometimes you see a beautiful theorem A that you love to talk about. Then another beautiful theorem B comes around, making the first one meaningless since B trivially...
From Computational Complexity
A New Cold War?
Imagine the following not-so-unrealistic scenario: The US-China trade war deepens leading to a cold war. The US blocks all Chinese citizens from graduate school...
From Computational Complexity