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 Gödel's Lost Letter and P=NP
A New AKS
An award for attacking an NP-hard problem Miklós Ajtai, Ravi Kumar, and D. Sivakumar were among winners of the ACM STOC 2023 “Test of Time” Awards. The award recognized...
From Gödel's Lost Letter and P=NP
A Hidden Heroine
William Friedman was famous as one who broke codes during both world wars. I knew about him from articles such as this. But wait His wife Elizebeth Smith Friedman...
From Gödel's Lost Letter and P=NP
Computer Science Marches On
With a note on the death of someone who tried to stop it Arnold the Allosaurus is moving to new digs. All during my time at Princeton, he held sway in cavernous...
From Gödel's Lost Letter and P=NP
A Little Noise Makes Quantum Factoring Fail
Jin-Yi Cai is one of the top theory experts in the world. Both Ken and I have had the pleasure to work with him and interact with him over the years. We have discussed...
From Gödel's Lost Letter and P=NP
Human Extinction?
And some counter-arguments Hava Siegelmann is the Provost Professor in the Manning College of Information and Computer Sciences at U.Mass. Amherst. She returned...
From Gödel's Lost Letter and P=NP
Topping the Hat
An “einstein” that doesn’t need flipping Siobhan Roberts is a Canadian science journalist, biographer, and historian of mathematics. She has an article that appeared...
From Gödel's Lost Letter and P=NP
Some Rice News
Lydia Kavraki is the Noah Harding Professor of Computer Science at Rice University. She is also professor of Bioengineering, professor of Electrical and Computer...
From Gödel's Lost Letter and P=NP
ACM Prize to Yael Kalai
Plus evocations of the roles of complexity and verification in crypto and human relations Yael Kalai has just been named the winner of the 2022 ACM Prize. She works...
From Gödel's Lost Letter and P=NP
Neil Jones, 1941–2023
Neil Jones, sad to relate, just passed away. He was Professor Emeritus of Computer Science at the University of Copenhagen, which he joined on a permanent basis...
From Gödel's Lost Letter and P=NP
The ChatGPT Conundrum
High absolute, low relative Kolmogorov complexity 4/1 prank source [Editors’ Note: Our usual blog format has the first paragraph lead with a human subject, but...
From Gödel's Lost Letter and P=NP
A New Tiling
With a flip and some twists Roger Penrose has been floored. And perhaps re-floored. Here he is standing on the floor of the Mitchell Institute of Texas A&M, which...
From Gödel's Lost Letter and P=NP
The 2022 Turing Award
Bob Metcalfe is the sole winner of the 2022 Turing Award. He keyed the development of Ethernet technology growing out of his PhD thesis while at Xerox PARC in the...
From Gödel's Lost Letter and P=NP
Problems Better Than Solutions
Defining the problem often means more than solving it Avrim Blum is the CAO at TTIC who got his degrees at MIT and then was at CMU almost for 25 years: CAO is Chief...
From Gödel's Lost Letter and P=NP
Céad Míle GPT
The gift of Broadscale Linguistic Affinely Regressed Neurally Encoded Yakking By Simplified from “leprechaun robot” Neil L. is sentient. As a fantastical creature...
From Gödel's Lost Letter and P=NP
SODA 2023
Traces of strings, plus ways of tracing accepted papers Anindya De was at Northwestern University and is now at the University of Pennsylvania—see here. He was...
From Gödel's Lost Letter and P=NP
Novel Proofs of the Infinitude of Primes
Can they inform computational complexity theory? Bill Gasarch and Christian Elsholtz both like primes and jokes and graphs and ways of sharing baked goods. Bill...
From Gödel's Lost Letter and P=NP
Why Study Logic?
Before and after it is mechanized… Peter Andrews is a Professor of Mathematics, Emeritus at Carnegie Mellon University (CMU) in Pittsburgh, Pennsylvania. He has...
From Gödel's Lost Letter and P=NP
Rabin-Scott Time
Nondeterminism—why did it take so long? 2010 interview src1, Society for Science src2 Michael Rabin and Dana Scott won the 1976 Turing Award. They obtained their...
From Gödel's Lost Letter and P=NP
Logicians are Everywhere
So where were they between 1720 and 1820? Helena Rasiowa was a famous logician from Poland. She visited Case Western Reserve University when I was an undergraduate...
From Gödel's Lost Letter and P=NP