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 Structure (or lack thereof) of Data
Many of the various "proofs" of P≠NP follow a common theme: Define an NP problem with a certain structure. Argue that any algorithm that solves that problem must...
From Computational Complexity
Complexity and Computability
The 5th Conference on Logic, Computability and Randomness is going on this week at Notre Dame. Because of teaching and other commitments I only was able to attend...
From Computational Complexity
Parallel Thinking
Guy Blelloch from CMU gave a distinguished talk last week at Northwestern on Parallel Thinking, a take on the Computational Thinking pagadigm from his past and...
From Computational Complexity
The Life of Martin Gardner 1914-2010
The math and science writer Martin Gardner passed away on Saturday. Gardner wrote the column Mathematical games for Scientific American from 1956 to 1981 and Scientific...
From Computational Complexity
The End of Numb3rs
Sunday marks the end of the TV series that deals with the numbers 4, 8, 15, 16, 23 and 42. Monday marks the end of the TV series called "24". But lets talk about ...
From Computational Complexity
Boycotting Arizona
I heard a suggestion that computer science conferences not be held in Arizona because of their new anti-immigration law. Both Bill and I have discussed academic...
From Computational Complexity
Goodbye PostScript
I was uploading a new PDF file up to my publications page and noticed that the paper also had a PostScript link but I didn't have an updated postscript file. So...
From Computational Complexity
Which Name Do You Play For?
A relative on Facebook posted the following note about baseball player Alex Rodriguez.He plays for the name on the back of the jersey [Rodriguez] and not the front...
From Computational Complexity
NSF at 60
On May 10, 1950, Harry Truman signed Public Law 507 creating the National Science Foundation based on Vannevar Bush's Science - The Endless Frontier. The NSF is...
From Computational Complexity
Is Complexity Math or Science?
In March David Pennock promoted Computer Science as STEAM (Science, Technology, Engineering, Arts and Mathematics) a takeoff on STEM. There are aspects of computer...
From Computational Complexity
Gadget Love
Many of my fellow CS theorists are surprisingly technophobes. Don't own a cell phone. Begrudgingly got a credit card but still refuse to buy anything online. Still...
From Computational Complexity
The Base of Computational Complexity
In the April CACM, George V. Neville-Neil wrote a column on a question about the foundations of computer science:In most areas of science there are a few basicdiscussion...
From Computational Complexity
Trading Money for Computation
Since the beginning of complexity we talked about time complexity t(n) as a function of the input size. But it has been the inverse of this function that we really...
From Computational Complexity
A Post on the Post Post
On Monday Richard Lipton wrote a nice piece on the work of Emil Post, a famous logician who had great results and even greater questions in the early days of recursion...
From Computational Complexity
Life without Flying
A reminder that registration for all three Cambridge conferences are now live: STOC (early registration deadline April 30), Complexity (May 3) and Electronic...
From Computational Complexity
The Pad
So I broke down and bought the iPad. Many people have asked whether the iPad is worth buying. The short answer: It will be.There are many many iPad reviews out...
From Computational Complexity
New Constructive Aspects of the Lov
Guest Post by Bernhard Haeupler The Lovász Local Lemma (LLL), slightly simplified, states that: Given a set of “bad” events, if for every event A there exists,...
From Computational Complexity
Choosing a Graduate School
Besides being tax day, Thursday is the deadline to decide where to attend graduate school. How should you choose? I've blogged on this topic before but a few recent...
From Computational Complexity