One nice aspect of Motwani and Raghavan's classic textbook, Randomized Algorithms, is that the notes for many chapters include open questions marked as "research problems." However, the textbook is ~20 years old at this point, and it's unclear what progress has been made on these problems in that time.

My question is whether there's a resource listing progress and resolution status of these problems, preferably with citations.

  • 1
    $\begingroup$ I would be surprised if there is a single resource that collects all of this, but if run into any problems you are particularly interested in, you could try asking a question here or on CSTheory about it (you might want to do a little bit of research, e.g., a literature search, before asking though). $\endgroup$ – D.W. Sep 13 '14 at 5:13
  • $\begingroup$ @D.W.: The whole point of this question was to ask about a general resource. If I were wondering about something specific of course I would've done what you suggested. $\endgroup$ – Huck Bennett Sep 13 '14 at 5:20
  • 3
    $\begingroup$ At the risk of being tautological, such a list exists only if somebody's written it. People don't tend to track that kind of thing. But if you produced a high-quality list, it would be a good resource: maybe Raghavan would link it from his webpage, even. $\endgroup$ – David Richerby Sep 13 '14 at 10:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.