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$
$\endgroup$
2
-
$\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$– user541686Jul 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$– Jake ShellmanJul 8, 2017 at 6:33
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
3
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
answered Jul 7, 2017 at 17:51
-
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$ 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$– codyJul 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$ Aug 7, 2018 at 14:18
$\begingroup$
$\endgroup$
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).
