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
The NIPS Experiment
The NIPS (machine learning) conference ran an interesting experiment this year. They had two separate and disjoint program committees with the submissions split...
From Computational Complexity
The Ethics of Saving Languages
The linguist John McWhorter wrote an NYT opinion piece entitled Why Save a Language? where he argues why we should care about saving dying languages, basically...
From Computational Complexity
Favorite Theorems Recap
We've now completed five decades of favorite theorems. 1965-1974 1975-1984 1985-1994 (PDF) 1995-2004 And to recap the ten we chose this year from 2005-2014 ...
From Computational Complexity
A November to Remember
The Imitation Game starring Benedict Cumberbatch as Alan Turing opens in the US on November 28. If you read this blog you should see that movie. If one challenged...
From Computational Complexity
From Homework Solution to Research Paper
Inspired by the Dantzig Story I occasionally put an open problem on a class assignment. Never worked, though I did have a student get a research paper from solving...
From Computational Complexity
George Dantzig >= 100
We celebrate the 100th anniversary of the birth of George Dantzig today. In his obituary post we talked about his work on optimization, particularly the simplex...
From Computational Complexity
Favorite Theorems: Circuit Lower Bounds
My long time blog readers should have no surprise on my final favorite theorem of 2005-2014. Nonuniform ACC Circuit Lower Bounds by Ryan Williams (PDF) We sawlist...
From Computational Complexity
Metrics in Academics
Congratulations to the San Francisco Giants, winning the World Series last night. In honor of their victory let's talk metrics. Baseball has truly embraced metrics...
From Computational Complexity
Sipser Symposium
On Sunday we had the Symposium on Theoretical Computer Science on the Occasion of Michael Sipser's 60th birthday to celebrate what Mike has brought to research...
From Computational Complexity
MSR SVC Letters
The Committee for the Advancement of Theoretical Computer Science put together an open letter to several research leaders at Microsoft. We feel that there should...
From Computational Complexity
The Curious Case of NP and NEXP
NP (nondeterministic polynomial time) and NEXP (nondeterministic exponential time) are provably different classes by the nondeterministic time hierarchy. No surprise...
From Computational Complexity
2014 Fall Jobs Post
Tis the season for the fall jobs post. Please list any jobs, academic or industrial, in theoretical computer science broadly construed in the comments to this post...
From Computational Complexity
Favorite Theorems: Multilinear Circuits
In the past decade we have seen a strong program in algebraic circuit complexity. If you just define circuits using multiplication and addition gates, sometimes...
From Computational Complexity
MikeFest
I rarely highlight individual events on the blog, but one's advisor only turns sixty once. We will honor Michael Sipser at MIT on Sunday, October 26 with a one...
From Computational Complexity
Typecasting in Dagstuhl
After this pre-recorded typecast, we learned of the tragic death of Alexey Chervonenkis, the C of VC dimension, a huge loss to the learning community. We’ll have...
From Computational Complexity
Goodbye MSR-SVC
This week I'm back at Dagstuhl for the Workshop on Algebra in Complexity Theory. Bill is here as well and we hope to have a typecast for you later this week. The...
From Computational Complexity
Richard Lipton Wins Knuth Prize
Georgia Tech professor and fellow blogger Richard Lipton will receive the 2014 Knuth Prize at the upcoming FOCS conference in Philadelphia. The Knuth Prize is given...
From Computational Complexity
Beyond the Commodity
Back in 2005 I lamented the fact that students viewed computers as a commodity, a tool they use, like an automobile, but have no reason to understand how or why...
From Computational Complexity
Favorite Theorems: Quantum Interactive Proofs
Practical quantum computing still has many hurdles to jump through, but the quantum computing model does generate great complexity questions and often surprising...
From Computational Complexity