Sources of open problems?

Question

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!

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)? — user541686, Jul 08 '17 at 00:40
I meant both, though it seems like the second set of problems is publishable yet easier to solve possibly. — Jake Shellman, Jul 08 '17 at 06:33

score 23 · Accepted Answer · answered Jul 07 '17 at 17:51

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.

In Computer Science (Wikipedia): https://en.wikipedia.org/wiki/List_of_unsolved_problems_in_computer_science
Sublinear time algorithms: http://sublinear.info/index.php?title=Main_Page
Analysis of Boolean Functions: http://lanl.arxiv.org/abs/1204.6447
Computational geometry: http://cs.smith.edu/~orourke/TOPP/
Exact algorithms: http://faculty.cs.tamu.edu/chen/courses/cpsc669/2011/notes/ww1.pdf
Formal languages, etc.: https://www.student.cs.uwaterloo.ca/~cs462/openproblems.html
Parameterized complexity: http://fpt.wikidot.com/open-problems
Topological graph theory: http://www.cems.uvm.edu/~darchdea/problems/problems.html
Embeddings of finite metric spaces: http://kam.mff.cuni.cz/~matousek/metrop.ps
Lambda calculus, proof theory, semantics, and programming languages: http://tlca.di.unito.it/opltlca/
Perfect graphs: http://www.aimath.org/WWN/perfectgraph/
Real analysis in computer science: https://simons.berkeley.edu/sites/default/files/openprobsmerged.pdf
Fine-grained complexity: http://duch.mimuw.edu.pl/~malcin/opl.pdf
Communication complexity: https://sublinear.info/index.php?title=Workshops:Banff_2017
Erdős problems: http://www.math.ucsd.edu/~erdosproblems/All.html

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! — Jake Shellman, Jul 08 '17 at 06:33
I'm surprised to see the TLCA open problems list without the closely related RTA problems: http://www.win.tue.nl/rtaloop/problems/summary.html — cody, Jul 08 '17 at 16:05
Roughly half of the open problems on fine grained complexity are in fact open problems on fixed-parameter algorithms =) — Alexander S. Kulikov, Aug 07 '18 at 14:18

score 8 · Answer 2 · edited Jun 17 '20 at 09:38

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

Sources of open problems?

2 Answers2

Linked