In the November 1989 issue of American Mathematical Monthly Yoram Sagher presented a note "Counting the Rationals" giving a simple 1-1 mapping from the...
Persi Diaconis once again shatters our belief in generating randomness; this time showing , with Susan Holmes and Richard Montgomery, that flipping coins does...
The first issue of 2004 of SIGACT News is out. The complexity column has part 2 of last issues' article on constraint satisfaction problems. More exciting is...
Persi Diaconis once again shatters our belief in generating randomness; this time showing , with Susan Holmes and Richard Montgomery, that flipping coins does...
This week I'm visiting the University of Calgary and although I have never been here before it seems like a homecoming. They have a strong quantum computing...
How will the trend in outsourcing programming work affect computer science departments in America? In the short term not good. A lesser need for programmers...
A Chicago Tribune editorial describes an incredibly bad restriction on publishing from Iran. The U.S. Treasury Department's Office of Foreign Assets Control...
How will the trend in outsourcing programming work affect computer science departments in America? In the short term not good. A lesser need for programmers...
A Chicago Tribune editorial describes an incredibly bad restriction on publishing from Iran. The U.S. Treasury Department's Office of Foreign Assets Control...
America's Favorite Binary Tree, the 2004 College Basketball Brackets have been released. This week last year had several posts related to the brackets...
As I had mentioned earlier , this year I plan to write My Favorite Ten Complexity Theorems of the Past Decade II. I decided to reveal the choices one per month...
As I had mentioned earlier , this year I plan to write My Favorite Ten Complexity Theorems of the Past Decade II. I decided to reveal the choices one per month...
When we see "natural" in a computer science papers it usually reflects an informal idea of realism, i.e., Clique is a natural NP-complete problem while 1-in-3...
Can you teach basic computer science concepts to children? Without a computer? Computer Science Unplugged by Tim Bell, Ian Witten and Mike Fellows has a...
The Newark Star-Ledger has an article about the downfall of AT&T research. Quantum Algorithms has some follow-up quotes by Bjarne Stoustrup. No doubt that...
Can you teach basic computer science concepts to children? Without a computer? Computer Science Unplugged by Tim Bell, Ian Witten and Mike Fellows has a...
Time for another of my favorite open questions: Is Boolean Formula Satisfiability (SAT) checkable? The best notion of program checking comes from a paper by...
Should public schools in the US teach creationism in addition to or in place of evolution? As a scientist I have to say "no," though I'm preaching to the choir...
In a comment on my last post , Suresh Vankat said "On the other hand, we teach school-age children Newtonian physics without laying out a careful argument why...
In a comment on my last post , Suresh Venkat said "On the other hand, we teach school-age children Newtonian physics without laying out a careful argument why...
Today starts the spring quarter at the University of Chicago and I start teaching undergraduate complexity. Many of the most beautiful concepts in theory get...
Today starts the spring quarter at the University of Chicago and I start teaching undergraduate complexity. Many of the most beautiful concepts in theory get...
Comments to my last post basically ask how has the introductory courses in theory has changed over the years. My first reaction: remarkably little. Theoretical...
Comments to my last post basically ask how has the introductory courses in theory has changed over the years. My first reaction: remarkably little. Theoretical...
A guest post from Dieter van Melkebeek This week, about 50 computer scientists gather at Schloss Dagstuhl for a seminar on "Complexity of Boolean Functions."...
A guest post from Dieter van Melkebeek This week, about 50 computer scientists gather at Schloss Dagstuhl for a seminar on "Complexity of Boolean Functions."...
Another Guest Post from Dieter van Melkebeek Thursday morning, Shuki Bruck gave the first talk at the workshop that dealt with actual Boolean circuits. He...
Another Guest Post from Dieter van Melkebeek Thursday morning, Shuki Bruck gave the first talk at the workshop that dealt with actual Boolean circuits. He...
The Blum speed-up theorem states that there exists a computable language L such that if L is in time t(n) then L is in time log(t(n)). The log function can be...
A friend of mine from college became a science writer for various newspapers and magazines. Once he told me about his two biggest complaints about scientists. ...
Having problems with message search?
Fill out this form to ensure your group is one of the first to be migrated to the new message search system.
