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
Libraries Without Books
Georgia Tech in its library renovation will move the vast majority of its books into a combined Emory/Tech Library Service Center off-campus. Very few people use...
From Computational Complexity
Announcements
Time for a short rundown of announcements. STOC will be held May 31-June 3 in New York City. Early registration and hotel deadline is April 30. Student travel...
From Computational Complexity
Should you reveal a P = NP algorithm?
A reader asks What would you do if you could prove that P=NP with a time-complexity of n2 or better... moreover, would you publish it? There are all theseheartbleed...
From Computational Complexity
Favorite Theorems: Extended Formulations
The first couple of favorite theorems took place at the beginning of the last decade, but recent years have brought exciting results as well, such as the limitations...
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