July Edition This is the August edition of Favorite Theorems. Perhaps you could easily find a satisfying assignment of a Boolean formula when only one solution...
A request from Claire Kenyon. We are finalizing the budget for FOCS 2007 in Providence. The traditional Saturday evening reception will cost at least $53 per...
What invention of the second half of the 20th century had the single greatest effect on global commerce? In a neat new book The Box , Marc Levinson makes a...
Claire's post on French Universities brings up an interesting point. In most countries universities are almost all funded and run by the national government....
Derandomizing an RP algorithm is like finding hay in a haystack. In that vein comes the following cartoon from the Danish paper Politiken (via Peter Bro...
FOCS registration is now available . Early registration deadline is September 18, hotel rooms held until September 29. SODA accepted papers have been posted ....
We all have 9/11 stories, here's mine, more of a 9/12 story. Prelude . I was packing up my hotel room in Wrzburg after the 1993 STACS conference. I flipped on...
In the seventh Complexitycast , Bill Gasarch returns to talk about approaches to research. MP3 (22 minutes, 3.9MB) -- Posted by Lance to Computational...
A student proves what I feel is quite a nice result but the student laments that the proof was easy, they had simply put together various tools from earlier...
Google for Yankees Magic Number and short down the list you'll find my 2004 post The Beauty of the Magic Number . As I write this the Yankees have 88 wins and...
My daughter started middle school and as parents we attended back to school night. In the evening we follow our daughters schedule and see her various...
The MacArthur Foundation named their 2006 Geniuses including Luis von Ahn , Carnegie-Mellon cryptography, who has worked in steganography but best known for...
Shing-Tung Yau, who doesn't like his portrayal in Sylvia Nasar and David Gruber's New Yorker article on the Poincar conjecture. So Yau, who apparently has ...
Boaz Barak reports that Bernard Chazelle has updated his essay The Algorithm: Idiom of Modern Science complete with bells, whistles, cartoons, PCP's and zero...
August Edition In the 70's we had essentially no super-polynomial lower bounds for natural problems on general circuits beyond depth 2. Two papers kick started...
A non-theorist saw the upcoming STOC call for papers and asked about the following line. Authors should submit an extended abstract (not a full paper). and...
Guest Post from Jrmy Barbay . In multi-authors publications from other fields (biology, physics), the order of the author's names roughly indicates the...
The last Electronic Commerce conference in June had a workshop on sponsored search . Sponsored search are those ads you see when you run a Google or Yahoo...
David Pennock, Yiling Chang and I created a Prediction Markets Map of the 2006 US Senates Elections. When you load the map it downloads the latest prices from...
Not the Conference on Computational Complexity but the Computing Community Consortium , a new organization funded by the NSF and organized by the Computing...
Quick quiz Can you submit a paper to a conference that you are not sure you can attend? You have agreed to give an invited talk at a conference. But you find ...
Recommendation Systems The big CS news of the week: Netflix , the online DVD subscription rental site, has announced a million-dollar prize for substantially ...
NPR's On the Media interviewed an old college friend of mine, science writer Vincent Kiernan, about his new book Embargoed Science . "Embargoed Science" refers...
Tis the season that my fellow professors and I start receiving collections of brochures, newsletters and posters from various CS departments around the...
I hate to keep secrets but in our field much of what we discuss should be kept confidential as much as possible. What do we need to keep quiet about? ...
My daughter's math text list natural numbers as {1,2,&hellip} and whole numbers as {0,1,2,&hellip}. I remembered them the other way around, after all "0" seems...
The ACM Symposium on Theory of Computing (STOC) will host its first Undergraduate Student Research Competition in 2007 sponsored by Microsoft Research. From...
Imagine back to the early 90's before we had a world-wide web. You had a new result, a nice result but not so important that you would do a mass email. You...
Last week's episode of Numb3rs The Mole had a mildly interesting academic side story. [Mild Spoiler Warning] Charlie, the mathematician, discovered that his...
September Edition What is the best a probabilistic algorithm can do for the worst-case input? Perhaps it might be easier to show the limitations of a ...
