From Open Problems in Sublinear Algorithms
Revision as of 05:02, 13 December 2012 by Krzysztof Onak (talk | contribs)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

Currently, editing the wiki requires an account with a confirmed email address. This was implemented in response to spambots and has been working pretty well so far. We may replace this requirement with CAPTCHAs in future.

If you see a typo, or you know how to make a question more clear, or you know of a missing citation, etc., help us improve the quality of this wiki! Please also do not take it personally, if some of your edits are later reverted.

Progress on problems[edit]

Since the problems were posed, some of them have been resolved and significant progress has been made on some other ones. If you know of such a case, please report it in a section “Update(s)” under the problem. See Problem 23 for an example.

Adding new problems[edit]

If you want to add a new open problem, go to the Waiting Room for instructions.

Editing bibliography[edit]

  • If you want to delete an entry from the bibliography, please email admin@sublinear.info. We will verify that no-one cites it and delete it.
  • To add an entry, first create an identifier, which has the form


    For instance if the authors are Cormode and Muthukrishnan, and the paper was published in 2005, then the default identifier is CormodeM-05. Is this identifier is already taken, use the first English letter x such that CormodeM-05x does not appear in the bibliography yet. Right now the resulting identifier would be CormodeM-05c.
  • Add {{bibentry|identifier|authors-title-etc}} to the bibliography.

Using the wiki[edit]

Cheat sheet[edit]

Citation [AlonMS-99,BlumLR-93
Math operators $\operatorname{poly}(n) \cdot \operatorname{polylog}(m)$
$\operatorname{poly}(n) \cdot \operatorname{polylog}(m)$
<ref>This is a footnote.</ref> creates a footnote. Remember to add

<references />

at the end of the page. See here for an example.