<p><strong>On sublinear algorithms:</strong> see <a href="https://sublinear.info/index.php?title=Open_Problems:By_Number" rel="noreferrer">Sublinear.info</a>.</p>
<p>This is a (maintained) compilation of open problems, gathered from workshops and conferences on sublinear time algorithms (streaming, property testing, etc.)</p>
<p><strong>On learning theory:</strong> see the open problems from COLT: <a href="http://proceedings.mlr.press/v30/#open-problem" rel="noreferrer">2013</a>, <a href="http://proceedings.mlr.press/v35/#open" rel="noreferrer">2014</a>, <a href="http://proceedings.mlr.press/v40/#open" rel="noreferrer">2015</a>, <a href="http://proceedings.mlr.press/v49/#open" rel="noreferrer">2016</a>.
COLT (<em>Conference On Learning Theory</em>) hosts a session dedicated to open problems, with a <a href="http://www.learningtheory.org/colt2017/for-authors-2/call-open-problems/" rel="noreferrer">call for participation</a> sent out every year:</p>
<blockquote>
<p>The write-up of an open problem should include:</p>
<ul>
<li><p>a clearly defined problem;</p>
</li>
<li><p>the motivation for studying the problem, with an argument why it is important and interesting;</p>
</li>
<li><p>the current state of this problem (including any known partial or conjectured solutions and relevant references).</p>
</li>
</ul>
</blockquote>

CC BY-SA 3.0
2017-07-07T17:30:45.013Z
2017-07-07T17:30:45.013Z
2020-06-17T09:38:08.363Z
Clement C.
<p>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: <a href="http://cstheory.stackexchange.com/questions/174/major-unsolved-problems-in-theoretical-computer-science/251#251">http://cstheory.stackexchange.com/questions/174/major-unsolved-problems-in-theoretical-computer-science/251#251</a>.</p>

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

CC BY-SA 3.0
2017-07-08T06:33:49.003Z
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
CC BY-SA 3.0
2017-07-08T16:05:42.750Z
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
CC BY-SA 4.0
2018-08-07T14:18:11.063Z
Roughly half of the open problems on fine grained complexity are in fact open problems on fixed-parameter algorithms =)
Alexander S. Kulikov
CC BY-SA 3.0
2017-07-07T17:51:03.127Z
2017-07-07T17:51:03.127Z
Huck Bennett
<p>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! </p>

<p>Thanks so much!</p>

CC BY-SA 3.0
2017-07-08T00:40:45.657Z
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
CC BY-SA 3.0
2017-07-08T06:33:08.113Z
I meant both, though it seems like the second set of problems is publishable yet easier to solve possibly.
Jake Shellman
<reference-request><soft-question>
Sources of open problems?
Jake Shellman
# Sources of open problems?

(Asked by: username_0 on 2017-07-07)

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!

**Tags:** reference-request, soft-question
> **Comments:**
> **username_1**: 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)?  
> **username_0**: I meant both, though it seems like the second set of problems is publishable yet easier to solve possibly.  

---

## 2 answers

### Answer by username_3 on 2017-07-07. Score: 23 | Accepted answer

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>

> **Comments:**
> **username_0**: 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!  
> **username_4**: 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  
> **username_5**: Roughly half of the open problems on fine grained complexity are in fact open problems on fixed-parameter algorithms =)  

---

### Answer by username_2 on 2017-07-07. Score: 8

**On sublinear algorithms:** see [Sublinear.info](https://sublinear.info/index.php?title=Open_Problems:By_Number).

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](http://proceedings.mlr.press/v30/#open-problem), [2014](http://proceedings.mlr.press/v35/#open), [2015](http://proceedings.mlr.press/v40/#open), [2016](http://proceedings.mlr.press/v49/#open).
COLT (*Conference On Learning Theory*) hosts a session dedicated to open problems, with a [call for participation](http://www.learningtheory.org/colt2017/for-authors-2/call-open-problems/) 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).


---

