This thread is another experiment roughly in the vein of the Boring Advice Repository and the Solved Problems Repository.
There are some topics I'd like to see more LW posts on, but I feel underqualified to post about them relative to my estimate of the most qualified LWer on the topic. I would guess that I am not the only one. I would further guess that there are some LWers who are really knowledgeable about various topics and might like to write about one of them but are unsure which one to choose.
If my guesses are right, these people should be made aware of each other. In this thread, please comment with a request for a LW post (Discussion or Main) on a particular topic. Please upvote such a comment if you would also like to see such a post, and comment on such a comment if you plan on writing such a post. If you leave a writing-plan comment, please edit it once you actually write the post and link to the post so as to avoid duplication of effort in the future.
Let's see what happens!
Edit: it just occurred to me that it might also be reasonable to comment indicating what topics you'd be interested in writing about and then asking people to tell you which ones they'd like you to write about the most. So try that too!
Hm...the set of NP-complete problems where there is a polynomial-time approximation scheme is not that large, and the approximation schemes can sometimes be pretty bad (i.e. getting answers within 1% takes time n^100). Besides, Bayesian inference is at least #P-complete, possibly P-space complete, and a 1% error in the prior blows up to arbitrarily large error in the posterior, so approximation algorithms won't do anyways.
I'm curious to learn more.
My general impression (having studied computer science, and complexity theory in passing, but being far from an expert) is that bounded-error approximations are not as well studied as precise solutions. I also get the impression that most of the bounded-error complexity results are results for specific approximation algorithms, not proofs about the limits of such algorithms. Are impossibility results for bounded-error approximations common?
In other words,
... (read more)