7
$\begingroup$

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!

$\endgroup$
  • $\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$ – Mehrdad Jul 8 '17 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$ – Jake Shellman Jul 8 '17 at 6:33
19
$\begingroup$

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.

$\endgroup$
  • 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$ – Jake Shellman Jul 8 '17 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 Jul 8 '17 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$ – Alexander S. Kulikov Aug 7 '18 at 14:18
6
$\begingroup$

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).

$\endgroup$

Your Answer

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

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