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
Memory is Hot
A good number of the faculty candidates interviewing at Georgia Tech have a common theme: Memory. Memory connected to databases, to programming languages, to...
From Computational Complexity
Lance and Bill Gather for Gardner
Every two years in Atlanta, recreational mathematicians gather to honor Martin Gardner, whose Scientific American column Mathematical Games through the 60's and...
From Computational Complexity
Almost Famous Quantum Polynomial Time
I have been playing with a new complexity class AFQP, defined in a yet-to-be-published manuscript by Alagna and Fleming. A language L is in AFQP if there is a polynomial...
From Computational Complexity
A Reduced Turing Award
A Turing machine has an extremely simple instruction set: Move left, move right, read and write. If you want to do real programming, you need something a bit...
From Computational Complexity
Stephen Hawking (1942-2018)
Stephen Hawking passed away earlier this morning in Cambridge, England. As a brilliant theoretical physicist and best-selling author all while dealing withA...
From Computational Complexity
Data-Driven Programming
Five years ago I posted about Flash Fill, a then new Microsoft Excel feature that would reformat data based on examples. I just checked the latest version of Excel...
From Computational Complexity
Me and My Bolt
On Tuesday I got a knock on my car's window. Rolling it down someone asked if I liked my car as he was thinking of buying one himself. Was I driving the...
From Computational Complexity
NP is Hard
You don't get much press by stating conventional beliefs--there is no "round earth society". Nevertheless there are serious researchers out there trying to sayI...
From Computational Complexity
Corporate Education
First of all read the #metoo testimonial going around the TCS blogosphere. Our field is not immune. Last Sunday Frank Bruni wrote an op-ed column Corporations,...
From Computational Complexity
For the Love of Algorithms
Wired magazine labelled 2017 as The Year We Fell Out of Love with Algorithms. The article goes on to talk about how algorithms give us filter bubbles, affect elections...
From Computational Complexity
Flying Blind
Many computer science conferences have made a number of innovations such as a rebuttal phase, multi-tiered program committees, a hybrid journal/conference model...
From Computational Complexity
From Art to Science
Q: Why did the neural net cross the road? A: Who cares along as it got to the other side. Whit Diffie and Martin Hellman in their classic 1976 paper talk about...
From Computational Complexity
A Sensitive Game
Last month I posted about the sensitivity conjecture and today I would like to talk about an interesting game developed by Gilmer, Koucký and Saks and independently...
From Computational Complexity
Donald Knuth Turns Eighty
We've kept this blog going long enough that we start repeating our celebrations. Ten years ago Bill celebrated Don Knuth's 70th Birthday and today Donald Knuthcelebrates...
From Computational Complexity
Complexity Year in Review 2017
Theorem of the year goes to the resolution of the dichotomy conjecture. I wrote about the conjecture in February and while the Feder et. al paper didn't hold up...
From Computational Complexity
Having Faith in Complexity
I believe P ≠ NP as much as anyone else. Nevertheless should we worry about trust we put in complexity? You don't need the full power of P = NP to break cryptography...
From Computational Complexity
Our AI future: The good and the Ugly
I don’t directly work in machine learning but one cannot deny the progress it has made and the effect it has on society. Who would have thought even a few years...
From Computational Complexity
Razor's Edge
Informally the sensitivity conjecture asks whether every hard Boolean function has a razor's edge input, where flipping a random bit has a reasonable chance ofrecent...
From Computational Complexity
Kolmogorov Complexity and the Primes
Bill's post on how to derive the non-finiteness of the primes from Van der Waerden's theorem reminds me of a nice proof using Kolmogorov complexity. A quick primer...
From Computational Complexity