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...
744
Lance
fortnow
Sep 1, 2006 7:51 pm
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...
745
Lance
fortnow
Sep 5, 2006 8:58 pm
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...
746
Lance
fortnow
Sep 6, 2006 7:31 pm
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....
747
Lance
fortnow
Sep 7, 2006 12:49 pm
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...
748
Lance
fortnow
Sep 8, 2006 3:30 pm
FOCS registration is now available . Early registration deadline is September 18, hotel rooms held until September 29. SODA accepted papers have been posted ....
749
Lance
fortnow
Sep 11, 2006 11:22 am
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...
750
Lance
fortnow
Sep 12, 2006 4:37 pm
In the seventh Complexitycast , Bill Gasarch returns to talk about approaches to research. MP3 (22 minutes, 3.9MB) -- Posted by Lance to Computational...
751
Lance
fortnow
Sep 13, 2006 10:36 am
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...
752
Lance
fortnow
Sep 14, 2006 1:15 pm
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...
753
Lance
fortnow
Sep 18, 2006 1:30 pm
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...
754
Lance
fortnow
Sep 19, 2006 12:38 pm
The MacArthur Foundation named their 2006 Geniuses including Luis von Ahn , Carnegie-Mellon cryptography, who has worked in steganography but best known for...
755
Lance
fortnow
Sep 20, 2006 1:53 pm
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 ...
756
Lance
fortnow
Sep 21, 2006 12:09 pm
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...
757
Lance
fortnow
Sep 24, 2006 5:04 pm
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...
758
Lance
fortnow
Sep 25, 2006 10:41 pm
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...
759
Lance
fortnow
Sep 26, 2006 8:59 pm
Guest Post from Jrmy Barbay . In multi-authors publications from other fields (biology, physics), the order of the author's names roughly indicates the...
760
Lance
fortnow
Sep 27, 2006 10:19 pm
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...
761
Lance
fortnow
Sep 28, 2006 2:17 pm
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...
762
Lance
fortnow
Oct 1, 2006 12:10 pm
Not the Conference on Computational Complexity but the Computing Community Consortium , a new organization funded by the NSF and organized by the Computing...
763
Lance
fortnow
Oct 3, 2006 12:29 pm
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 ...
764
Lance
fortnow
Oct 4, 2006 1:11 pm
Recommendation Systems The big CS news of the week: Netflix , the online DVD subscription rental site, has announced a million-dollar prize for substantially ...
765
Lance
fortnow
Oct 5, 2006 11:52 am
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...
766
Lance
fortnow
Oct 7, 2006 9:36 pm
Tis the season that my fellow professors and I start receiving collections of brochures, newsletters and posters from various CS departments around the...
767
Lance
fortnow
Oct 9, 2006 6:33 pm
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? ...
768
Lance
fortnow
Oct 10, 2006 7:41 pm
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...
769
Lance
fortnow
Oct 12, 2006 3:41 am
The ACM Symposium on Theory of Computing (STOC) will host its first Undergraduate Student Research Competition in 2007 sponsored by Microsoft Research. From...
770
Lance
fortnow
Oct 13, 2006 11:06 am
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...
771
Lance
fortnow
Oct 16, 2006 1:10 am
Last week's episode of Numb3rs The Mole had a mildly interesting academic side story. [Mild Spoiler Warning] Charlie, the mathematician, discovered that his...
772
Lance
fortnow
Oct 16, 2006 9:19 pm
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 ...