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
I am Bill Gasarch
I have a confession to make. Remember back in 2007 when I retired from the blog for about a year. I didn't actually retire at all but instead took the blog innew...
From Computational Complexity
Should We Have a TCS Ethics Board?
We sometimes hear of the (rare) scientist who fakes data or results of experiments. In theoretical computer science one cannot fake a theorem, particularly an important...
From Computational Complexity
Spring Breaking at Dagstuhl
It's spring break at Georgia Tech and time to head to Germany for the Dagstuhl Seminar Computational Complexity of Discrete Problems. Lots of discussion on...
From Computational Complexity
Cosmos from Generation to Generation
During high school, well before the world-wide web with its bloggers and YouTube, out came a series Cosmos that I watched religiously. Back then you had to watch...
From Computational Complexity
Favorite Theorems: Unique Games
Michel Goemans and David Williamson made a splash in the 90's using semidefinite programming to give a new approximation algorithm for the max-cut problem, a ratio...
From Computational Complexity
Why Become a Professor
Someone took me to task because in November I posted that the CRA News had 50 pages of job ads but didn't note that very few of those ads specifically were searching...
From Computational Complexity
Analog Adventures
I was 11 forty years ago when Dungeons and Dragons first appeared and by high school many of my friends spent far too many hours embarking on those fantasy adventures...
From Computational Complexity
IEEE and the Conference on Computational Complexity
Dieter van Melkebeek, current conference chair of the IEEE Conference on Computational Complexity has set up a forum to discuss the future affiliation of the conference...
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