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
A Deadly Side of Complexity
Better algorithms can lead to better medicine and save lives. Just today Tim Gowers discusses Emmanuel Candès' ICM Plenary Lecture, which among other things describes...
From Computational Complexity
Turing's Oracle
My daughter had a summer project to read and summarize some popular science articles. Having heard me talk about Alan Turing more than a few times, she picked a...
From Computational Complexity
Complexity versus Algorithms: The FOCS Challenge
In recent years, I've heard complaints from my complexity colleagues that FOCS and STOC are mostly algorithms and from the algorithm buddies that STOC and FOCSFOCS...
From Computational Complexity
Favorite Theorems: Limited Independence
When can limited randomness act as well as true random bits? Polylogarithmic independence fools AC0 circuits by Mark Braverman (JACM 2010) To explain this result...
From Computational Complexity
Subhash Khot wins Nevanlinna
At the opening ceremonies of the International Congress of Mathematicians in 2014, Subhash Khot was awarded the Rolf Nevanlinna Prize, given every four years to...
From Computational Complexity
The Burden of Large Enrollments
This week I'm at the CRA Snowbird conference, the biennial meeting of CS chairs and other leaders in the field. In 2012 many of the discussion focused on MOOCS....
From Computational Complexity
Elfdrive
New York Times, dateline June 11, 2019 With a near record-setting investment announced last week, the self-driving car service Elfdrive is the hottest, mostpiece...
From Computational Complexity
Favorite Theorems: Compressing the Local Lemma
Not only did Moser give a near optimal construction, but he did so in my favorite STOC talk of the decade. A Constructive Proof of the Lovász Local Lemma by Robin...
From Computational Complexity
Four Centuries of Logarithms
I just returned from visiting my former student Rahul Santhanam in Edinburgh. The National Museum of Scotland has an exhibit on logarithms, first published in...
From Computational Complexity
Computer Dating
My brother went through his old stuff cleaning out his apartment in New York and stumbled upon the 1981 computer dating questionnaire I wrote in high school. Forgive...
From Computational Complexity
Favorite Theorem: PCP Simplified
The famous Probabilistically Checkable Proof Theorem due to Arora, Lund, Motwani, Sudan and Szegedy states that every problem in NP has a proof that can be checked...
From Computational Complexity
CCC 2014
I'm returning from the 2014 IEEE Conference on Computational Complexity in Vancouver, unfortunately missing the last day. Several very nice talks including a wonderful...
From Computational Complexity
Wassily Hoeffding 1914-1991
In honor of the 100th anniversary of the birth of Wassily Hoeffding today, let's recall his incredibly useful inequality. Prob(|X-pn|>εn) < 2e-2ε2n where...
From Computational Complexity
STOC 2014
At the just completed STOC conference I received the 2014 SIGACT Distinguished Service Prize. Part of this citation reads"His blog, and many others that followed...
From Computational Complexity
Forgotten but not Lost in a Mapless World
Massimo Vignelli passed away on Tuesday, a visionary designer known for many things in particularly the 1970s NYC Subway Map. I used to pour over this map assteering...
From Computational Complexity
Theory Jobs 2014
In the fall we list theory jobs, in the spring we see who got them. Similar to last year, I created a fully editable Google Spreadsheet to crowd source who is going...
From Computational Complexity
Losing the Middle
In the 70's growing up, to listen to music I had a turntable for vinyl records. The quality of music went up almost continuously with the amount you were willing...
From Computational Complexity
1984 + 30
Back in 7th grade we had some discussion in history class long since forgotten but was ended by the statement "Remember, 1984 is only eight years away". While the...
From Computational Complexity
(IEEE) Conference on Computational Complexity
The 29th IEEE Conference on Computational Complexity will be held in Vancouver June 11-13. Student travel award deadline is TOMORROW Monday May 5th, early registration...
From Computational Complexity