Blogroll | Communications of the ACM

From My Biased Coin

Old References

One interesting aspect of our WSDM paper is that we have multiple references from the 1930's and 40's. It turns out our problem is related to some of the problems... Michael Mitzenmacher
From My Biased Coin | October 20, 2009 at 09:24 AM

From My Biased Coin

WSDM Paper : Acceptance Rates

I'm happy to announce our paper "Adaptive Weighing Designs for Keyword Value Computation" -- by me, John Byers, and Georgios Zervas -- was accepted to WSDM 2010... Michael Mitzenmacher
From My Biased Coin | October 19, 2009 at 04:08 PM

From My Biased Coin

Harvard Finances

For those who are interested in such things, Harvard's latest financial report appears to be available. Rumors have it that the report was made (widely) public... Michael Mitzenmacher
From My Biased Coin | October 18, 2009 at 06:21 PM

From My Biased Coin

Welcoming Myself to CACM

I'd like to welcome myself to the Blogroll for the Communications of the ACM! My colleague Greg Morrisett suggested I get my blog into the CACM Blogroll, so asome... Michael Mitzenmacher
From My Biased Coin | October 16, 2009 at 09:36 AM

From Computational Complexity

Thanks for the Fuzzy Memories

In the 1990's Manindra Agrawal and V. Arvind published a paper claiming that if SAT is reducible to a (non-uniform) weighted threshold function then P = NP. Their... Lance
From Computational Complexity | October 15, 2009 at 04:59 PM

From My Biased Coin

New Book on Concentration Bounds

I spent an hour or more today perusing the book Concentration of Measure for the Analysis of Randomized Algorithms, by Devdatt Dubhashi and Alessandro Panconesi... Michael Mitzenmacher
From My Biased Coin | October 15, 2009 at 02:47 AM

From The Eponymous Pickle

Bar Code Scanning for the iPhone

I finally took a look at the Redlaser barcode scanner from Occipital for the IPhone, released earlier this year. It is a $1.99 application that downloads quickly... Franz Dill
From The Eponymous Pickle | October 14, 2009 at 09:26 AM

From My Biased Coin

SOSP congratulations

One conference I've never had a paper in -- though I'd like to someday -- is SOSP, the Symposium on Operating Systems Principles, one of the flagship conferences... Michael Mitzenmacher
From My Biased Coin | October 13, 2009 at 10:50 AM

From Computational Complexity

The Molly Solution

This week Bill and I are both at the Dagstuhl Workshop on Algebraic Methods in Computation Complexity. I'll try to cover some of the talks and discussions on the... Lance
From Computational Complexity | October 12, 2009 at 05:12 PM

From Computational Complexity

Complexity Vidcast 2

Bill and I battle it out over what should be taught in a complexity course in our new vidcast. Lance
From Computational Complexity | October 9, 2009 at 05:14 PM

From My Biased Coin

PCing

This week I got my batches of papers to review for NSDI and LATIN. If I'm quiet for a while, I'm busy reading (and writing reviews). Needless to say, I didn't... Michael Mitzenmacher
From My Biased Coin | October 9, 2009 at 10:50 AM

From Computational Complexity

Publicity for P versus NP

On the New York Times website, John Markoff writes an article Prizes Aside, the P-NP Puzzler has Consequences motivated by my CACM article on The Status of the.... Lance
From Computational Complexity | October 8, 2009 at 05:14 PM

From My Biased Coin

More Harvard Classes Available Online

Thanks to the Harvard Extension School, the lectures for several more Harvard courses have been put online. My understanding is that these are classes taught at... Michael Mitzenmacher
From My Biased Coin | October 7, 2009 at 10:51 AM

From Computational Complexity

You are coordially invited... Why?

When you get an invitation via email should you accept? How well targeted is it? Some real examples that I got. EXAMPLE ONE: I would like to invite you toclick... GASARCH
From Computational Complexity | October 6, 2009 at 05:15 PM

From Computational Complexity

Two Recent Complexity Books omit Mahaney's theorem- ovesight or wisdom?

In a prior post (a while back) I pondered if Mahaney's theorem (SAT \le_m S, S Spare, implies P=NP) should be taught in a basic grad course in complexity. I thought... GASARCH
From Computational Complexity | October 5, 2009 at 05:16 PM

From My Biased Coin

Job Competitions

Stefan Savage made an insightful comment related to the issue of jobs: I've long felt that its a fallacy that there exists a fine-grained Platonic ideal of "goodness"... Michael Mitzenmacher
From My Biased Coin | October 5, 2009 at 10:51 AM

From My Biased Coin

"Core" TCS

Enough time has perhaps passed from Mihai's controversial post to consider, constructively I hope, some of the comments that arose here on this blog from it.One... Michael Mitzenmacher
From My Biased Coin | October 4, 2009 at 10:52 AM

From Computational Complexity

On Being Narrow

In a tweet a few days ago, David Bacon wonders why everyone always assumes all he can do is quantum computing? Oh, because that's all he's done. Time to do something... Lance
From Computational Complexity | October 2, 2009 at 05:16 PM

From My Biased Coin

Semantic Communication, Madhu Sudan

Madhu Sudan gave a colloquium at Harvard yesterday on his work on Universal Semantic Communication and Goal-Oriented Communication (both with Brendan Juba, thehere... Michael Mitzenmacher
From My Biased Coin | October 2, 2009 at 10:55 AM

From Computational Complexity

The Journal Manifesto 2.0

Reminder: FOCS early registration deadline today. Go here Below is a revised version of the Journal Manifesto. I restate the key sentence from my last post and... GASARCH
From Computational Complexity | October 1, 2009 at 05:16 PM