15
$\begingroup$

In the conference on learning theory (COLT), a list of open problems is published every year, for example, the list of 2019.

The open problems are being submitted and peer reviewed, which makes this list reliable (in the sense that the problems are well-defined, motivated and "accessible").

In the area of sublinear algorithms and property testing, there is this wiki page, which similarity includes a list of open problems.

My question is: are there similar lists for other areas in TCS (e.g. complexity, cryptography etc.)? I didn't find such a list in common conferences, and I wonder if there are blogs/websites with a list of known open problems (which are accessible in some sense, i.e. not just "p,np" and problems at that level)

Improve this question
$\endgroup$
3
  • 2
    $\begingroup$ Like this? cstheory.stackexchange.com/q/1015/129 $\endgroup$
    – Joshua Grochow
    Jun 17, 2020 at 15:39
  • 2
    $\begingroup$ Also: cstheory.stackexchange.com/questions/38560/…. $\endgroup$
    – Huck Bennett
    Jun 17, 2020 at 17:12
  • 2
    $\begingroup$ thanks! I am aware of those lists. My question is about either maintained projects (such that the sublinear algorithms project), or about peer reviewed sources (such as the COLT one). A blog of a known researcher for example, or a project maintained by a community of reputable authors $\endgroup$
    – Johana T.
    Jun 17, 2020 at 17:47

3 Answers 3

Reset to default
4
$\begingroup$

There is a list of open problems in computational geometry. It is edited and maintained by Demaine, Mitchell, and O'Rourke.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks, I will add this source to the question $\endgroup$
    – Johana T.
    Jun 18, 2020 at 19:08
  • $\begingroup$ This was one of the resources I linked to in the list above. $\endgroup$
    – Huck Bennett
    Jun 22, 2020 at 14:26
3
$\begingroup$

There is a list of open problems in graph theory and combinatorics collected and maintained by Douglas B. West.

This page maintains a list of lists of open problems in parameterized complexity.

Improve this answer
$\endgroup$
1
  • $\begingroup$ The parameterized complexity page also appears in the list I linked to above. $\endgroup$
    – Huck Bennett
    Jun 22, 2020 at 14:27
2
$\begingroup$

There's the TLCA List of Open Problems, collecting unsolved problems in $\lambda$-calculi and related areas, such as proof theory, semantics and theory of programming languages. It is maintained by Ryu Hasegawa, Luca Paolini and Paweł Urzyczyn.

There's also a related list, the RTA list of open problems, concerning rewriting theory. At some point it was maintained by Nachum Dershowitz and Ralf Treinen, but it seems to have not been updated in a while.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Both lists don't seems to be under active and recent curation. That's a shame, since so many new and interesting new open problems have shown up in the last decade. $\endgroup$
    – Martin Berger
    Jun 24, 2020 at 14:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.