Professor X and Professor Y from the same university attend the same conference. At the end of the conference, Professor X says in a surprised tone "That's the...
We lost a great complexity theorist over the weekend. From Phokion Kolaitis: It is with great sadness that I write to inform you that Larry Stockmeyer passed...
Fix a constant k. In 1982 Ravi Kannan showed that some 2 p 2 p language must not have n k -size (nonuniform) circuits. Here is a proof sketch: A simple...
Suppose you have some partial solutions of a popular problem. At what point do you announce your results? If you announce your partial results you run the risk...
Currently on airplanes children under two can ride free by sitting on a parent's lap. The FAA is considering whether to require such children to have their own...
Just over a year ago the Department of Defense cancelled their program on using markets to predict future world events, an overreaction that stopped funding a...
Keeping with this week's theme of prediction, I just finished reading The Wisdom of Crowds written by New Yorker writer James Surowiecki. The book makes the...
July Edition Consider a simple Arthur-Merlin game: Arthur probabilistically chooses a string r sends it to Merlin who responds with y and then Arthur runs some...
Disney World has two areas originally designed to give a glimpse of "the future", Tommorowland in Magic Kingdom and Future World at EPCOT, which itself once...
An upcoming FOCS paper is drawing a lot of interest at TTI and Chicago, Cryptography in NC 0 by Benny Applebaum, Yuval Ishai and Eyal Kushilevitz. Don't let...
Today I gave the talk at the Atlantic Theory Seminar , not Atlantic as in ocean but Atlantic , Iowa (population 7,257). Located halfway between the theory...
Today I gave the talk at the Atlantic Theory Seminar , not Atlantic as in ocean but Atlantic , Iowa (population 7,257). Located halfway between the theory...
Considerable Slashdot discussion about a Technology Review article Is Encryption Doomed? subtitled Our entire information society rests on a fragile foundation...
As everyone knows from the 2000 election, the United States does not use a majority rule to choose the president, rather they use a more complicated system...
My six-year old daughter playing with her friend on the computer ran into some problems. So she found me in the house and said, "Daddy, I know you are a...
Dieter van Melkebeek and I had a mild disagreement over an issue in writing a paper and he suggested I discuss it on my weblog. So here goes. We're working on...
August Edition In coding theory, one typically maps a string to a code such that with some small amount of error in the code one can still recover the original...
It is no secret that undergraduate enrollments in computer science have been dropping over the past five years. Students follow the money and, with the...
Computer Scientists have communicated via email since the mid-1980's. Back then email worked quite well: You would send a message and usually get a quick...
Arden Bement, who has been serving as the acting director of the National Science Foundation since Rita Colwell stepped down in February, has been nominated ...
A couple of interesting workshops happening this week both studying information, not the usual classical notions of information but quantum and random...
Baseball has a large number of mathematical nuggets but since my childhood I have always liked the simplicity of the magic number. In a division race, the...
Another literary reference to a hard combinatorial problem. Jonathan Safran Foer describes plans for a wedding reception in his disjointed novel Everything is...
I usually avoid politics in this weblog but I cannot totally ignore the US presidential election happening slightly more than a month from now. But nothing I...
From a comment on my last post . I think most computer scientists, even conservatives vote Democrat for one reason. Democrats fund the NSF, and the NSF gives...
Congratulations to Daphne Koller , this year's MacArthur Fellow in computer science. Koller uses a strong mathematical approach to decision making and...
I heard the following from a senior economist recently. A researcher at the beginning of his career has to please others. In order to receive a Ph.D., get a...
Steve Smale talked about his experiences in the Economics Theory Workshop at Chicago, particularly the aggressive questioning. I didn't attend his talk but I...
Ron Fagin asked me to announce two public commemorations of Larry Stockmeyer and his work. The first will be held at the IBM Almaden Research Center on Monday,...
Can one use a comic book and a toy to teach a complicated subfield of mathematics? Why knot? -- Posted by Lance to My Computational Complexity Web Log at...
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.
