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
Favorite Theorems: Connecting in Log Space
We start the favorite theorems with a result that might surprise many is still less than ten years old. Undirected Connectivity in Log-Space by Omer ReingoldPDF...
From Computational Complexity
Snow Days
An unexpected snowstorm hits the city in the middle of a workday. The roads get hopelessly clogged and I'm lucky to get home--many others just abandoned theirguarantees...
From Computational Complexity
What will we wrought?
When I went to college in the early 80's, students protested against college endowments invested in companies that had business in apartheid South Africa. My mother...
From Computational Complexity
Favorite Theorems: Introduction
I was invited to give a talk at the FST&TCS conference held in December 1994 in Madras (now Chennai). As I searched for a topic, I realized I was just finishing...
From Computational Complexity
Is Traveling Salesman NP-Complete?
[Nina Balcan asked me to mention that the COLT submission deadline is February 7] Jean Francois Puget writes a controversial post No, The TSP Isn't NP Complete...
From Computational Complexity
2013 Complexity Year in Review
The complexity result of the year goes to The Matching Polytope has Exponential Extension Complexity by Thomas Rothvoss. Last year's paper of the year showed that...
From Computational Complexity
To Write, or Not to Write, That Is the Question
Guest post by Vijay Vazirani Our field has been blessed with some great books: classics such as Knuth's volumes and Garey & Johnson literally got the field going...
From Computational Complexity
Security Changes
A couple of policy changes recently, one that supposedly enhances privacy and another that could reduce it. Google has been implementing perfect forward secrecy...
From Computational Complexity
Approximate Computing
Hadi Esmaeilzadeh is the newest professor in the School of Computer Science at Georgia Tech. Hadi works in computer architecture and did some great work on dark...
From Computational Complexity
Bitcoins Revisited
Two years ago I gave a lecture and posted about bitcoin. Of course what I didn't do was buy a bitcoin whose value back then was about $3 and today runs in the $1000...
From Computational Complexity
The New Patrons
A few centuries ago if you wanted to do science and not independently wealthy you needed help. Most of the important astronomers and natural philosophers (as well...
From Computational Complexity
Local Reductions
With the STOC deadline passing on Monday, now is a good time to look at the arXiv to see what has been posted since then. Hamid Jahanjou, Eric Miles and Emanuele...
From Computational Complexity
A Theorist Goes to SOSP
Monday I attended the 24th Symposium on Operating Systems Principles, the lead conference for computer systems research. Why would a nice theorist go to SOSP? Trying...
From Computational Complexity
Andrzej Mostowski (1913-1975)
Andrzej Mostowski was born 100 years ago today. While Mostowski worked in many areas of logic, including early fundamental work on model theory, for our readers...
From Computational Complexity
Science and Humanities
David Hollinger, a historian, wrote a recent Chronicle Review article The Wedge Driving Academe's Two Families Apart: Can STEM and the human sciences get along?...
From Computational Complexity
2013 Fall Jobs Post
Time again for the annual fall jobs post. As always the best places to look for academic CS positions are the job sites at the CRA and the ACM. Also check out the...
From Computational Complexity
Shut Down
The NSF core proposal in theoretical computer science, or Algorithmic Foundations as the NSF calls it hs three deadlines this academic year: Medium proposals (...
From Computational Complexity
Celebrating Maths in Oxford
This week I'm in Oxford for the opening of the new Andrew Wiles Mathematical Institute building and the Clay Research Conference including on workshop on New....
From Computational Complexity
Complexity and FOCS
The Conference on Computational Complexity Call for Papers is out, deadline November 27. The deadline for early registration and hotel for the FOCS conferenceavailable...
From Computational Complexity