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. ...
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. ...
The University of Chicago Bookstore has asked for textbook requests for the fall quarter by the middle of next month instead of during the summer as in past...
The University of Chicago Bookstore has asked for textbook requests for the fall quarter by the middle of next month instead of during the summer as in past...
March Edition Primality is a problem hanging onto a cliff above P with its grip continuing to loosen each day. - Paraphrased from a talk given by Juris...
March Edition Primality is a problem hanging onto a cliff above P with its grip continuing to loosen each day. - Paraphrased from a talk given by Juris...
Many years ago, an Israeli graduate student made the rounds and gave talks at several US universities. When he arrived in Chicago, he asked me if Americans...
Many years ago, an Israeli graduate student made the rounds and gave talks at several US universities. When he arrived in Chicago, he asked me if Americans...
Alan Kay will receive the 2004 Turing award . It can't always be a theorist. Registration is open for the 2004 Conference on Computational Complexity . The...
From Bill Gasarch: There are some more novelty songs about theory (aside from THE LONGEST PATH ) from the Washington CSE Band . The best one is THEORY GIRL . ...
From the PODC mailing list via Harry Buhrman. Usually the winners are kept secret until the ICALP or STOC conference but the PODC mailing list has already...
From Bill Gasarch: There are some more novelty songs about theory (aside from THE LONGEST PATH ) from the Washington CSE Band . The best one is THEORY GIRL . ...
The Unofficial Guide to Walt Disney World 2004 gives a lesson on complexity by describing the optimal tour of the Magic Kingdom as a traveling salesman...
A reader asks why Gafni and Borowski did not publish their paper in a journal and become eligible for the Gdel Prize . I wish this was an isolated incident but...
A reader asks why Gafni and Borowski did not publish their paper in a journal and become eligible for the Gdel Prize . I wish this was an isolated incident but...
Some required reading if you haven't seen it yet, a New York Times article on how America has lost some of its scientific leadership role over the rest of the...
Some required reading if you haven't seen it yet, a New York Times article on how America has lost some of its scientific leadership role over the rest of the...
I'm moving my web hosting service--if you can read this you are accessing the new host. I will wait a day or two to post again until the changeover is...
A readers asked about the complexity of games like Go and Chess. David Eppstein has a nice site giving a short description and references to a number of...
The Journal of the ACM has started asking for page charges. Author's institutions or corporations are requested to honor a page charge of $60.00 per printed...
A readers asked about the complexity of games like Go and Chess. David Eppstein has a nice site giving a short description and references to a number of...
The Journal of the ACM has started asking for page charges. Author's institutions or corporations are requested to honor a page charge of $60.00 per printed...
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.
