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
Degree and Sensitivity
Hao Huang's proof of the sensitivity conjecture that I posted on last week relied on a 1992 result of Gotsman and Linial. Let's talk about that result. Consider...
From Computational Complexity
Local Kid Makes History
The blogosphere is blowing up over Hao Huang's just posted proof of the sensitivity conjecture, what was one of the more frustrating open questions in complexity...
From Computational Complexity
FCRC 2019
Georgia Tech FCRC Participants I'm heading home from the 2019 ACM Federated Computing Research Conference in Phoenix, a collection of computer science meetings...
From Computational Complexity
The Urban/Rural Collegiality Divide
Just a reminder that Grigory Yaroslavtsev has taken over the Theory Jobs Spreadsheet. Check out who is moving where and let everyone know where you will continue...
From Computational Complexity
Compressing in Moscow
This week finds me in Moscow for a pair of workshops, the Russian Workshop on Complexity and Model Theory and a workshop on Randomness, Information and Complexity...
From Computational Complexity
What Happened to the Surprising Theorems?
Twenty-five years ago Peter Shor presented a polynomial-time factoring algorithms for quantum computers. For Peter, it was a simple translation of a quantum algorithm...
From Computational Complexity
NSF Panels
The government shut down in January led to delays at the National Science Foundation and only recently announcing decisions on grants submitted last fall. For those...
From Computational Complexity
Logic Then and Now
This week I attended the Association of Symbolic Logic North American Annual Meeting in New York City, giving a talk on P v NP. First I must share the announcement...
From Computational Complexity
Getting Through the Clutter
My daughter showed up at her doctor's office the other day and found it closed. She complained that she had received all these alerts, texts, emails, voicemails...
From Computational Complexity
Multiple Provers
Just over thirty years ago on May 5, 1989, I defended my PhD Thesis Complexity-Theoretic Aspects of Interactive Proof Systems. It's starts off with a parable for...
From Computational Complexity
The Next Chapter
I've accepted a position as Dean of the College of Science at the Illinois Institute of Technology in Chicago starting in August. It's an exciting opportunity...
From Computational Complexity
Geo-Centric Complexity
An interesting discussion during Dagstuhl last month about the US-centric view of theory. Bad enough that all talks and papers in an international venue are inManhattan...
From Computational Complexity
Physics of Everday Life
Based on Scott's review, I read through Stephen Pinker's Enlightenment Now. I can't top Scott's exposition of the book, but it is pretty incredible how far humanity...
From Computational Complexity
Cuckoo Cycles
Guest Blog by John Tromp (Thanks for the opportunity, Lance) In the past few months, cycle finding has become one of the most widely run graph theory problems....
From Computational Complexity
Scooped
At Dagstuhl I got a few ideas for future posts but then... We had some discussions about STOC allowing program committee members to submit papers that I planned...
From Computational Complexity
Back at Dagstuhl
Participants and Their Research Interests This week I'm in Germany for the Dagstuhl workshop on Computational Complexity of Discrete Problems well timedtypecast...
From Computational Complexity
Captain Einstein
If the president of the United States uses "complexity" in a tweet, I can't leave it alone. Airplanes are becoming far too complex to fly. Pilots are no longer...
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