I'm wondering if there are some known sources of open TCS problems? I'm a junior studying math/CS and would like to know of some accessible problems that I could start thinking about!

Thanks so much!

  • $\begingroup$ By "open problems" do you mean problems that have been attempted but not solved, or problems that people haven't even gotten around to solving yet (potentially because they're new or weren't interesting)? $\endgroup$
    – user541686
    Commented Jul 8, 2017 at 0:40
  • 1
    $\begingroup$ I meant both, though it seems like the second set of problems is publishable yet easier to solve possibly. $\endgroup$ Commented Jul 8, 2017 at 6:33

2 Answers 2


Here's a partial list of collections of open problems in TCS, broadly construed. Note that a collection of "major open problems" exists already on this site: http://cstheory.stackexchange.com/questions/174/major-unsolved-problems-in-theoretical-computer-science/251#251.

  • 1
    $\begingroup$ Thanks for this answer. I'll probably mark it as the final answer (I'll give it a couple more days). This is really amazing though! $\endgroup$ Commented Jul 8, 2017 at 6:33
  • 1
    $\begingroup$ I'm surprised to see the TLCA open problems list without the closely related RTA problems: win.tue.nl/rtaloop/problems/summary.html $\endgroup$
    – cody
    Commented Jul 8, 2017 at 16:05
  • 1
    $\begingroup$ Roughly half of the open problems on fine grained complexity are in fact open problems on fixed-parameter algorithms =) $\endgroup$ Commented Aug 7, 2018 at 14:18

On sublinear algorithms: see Sublinear.info.

This is a (maintained) compilation of open problems, gathered from workshops and conferences on sublinear time algorithms (streaming, property testing, etc.)

On learning theory: see the open problems from COLT: 2013, 2014, 2015, 2016. COLT (Conference On Learning Theory) hosts a session dedicated to open problems, with a call for participation sent out every year:

The write-up of an open problem should include:

  • a clearly defined problem;

  • the motivation for studying the problem, with an argument why it is important and interesting;

  • the current state of this problem (including any known partial or conjectured solutions and relevant references).


Your Answer

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

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