# Tag Info

10

This is an interesting (and surprising) example for a P $\to$ NP-hard $\to$ P $\to$ NP-hard $\to \cdots$ phase transition: Deciding if a complete graph on $n$ vertices, in which each vertex has a strict ranking of all other vertices, admits a popular matching is in P for odd $n$ and NP-hard for even $n$. (The parameter is the vertex number $n$.) The ...

5

I'm not sure how to answer (1), but (2) is known to imply circuit lower bounds against NQP (non-deterministic quasi-polynomial time). This is from Cody Murray and Ryan Williams' STOC 2018 paper. In fact, they show that these lower bounds follow from faster algorithms for what they call Gap Circuit Unsatisfiability: given a circuit $C$ on $n$ variables and ...

5

Refolding an unfolded origami is NP-hard.

4

There is a list of open problems in computational geometry. It is edited and maintained by Demaine, Mitchell, and O'Rourke.

4

3

There is a list of open problems in graph theory and combinatorics collected and maintained by Douglas B. West. This page maintains a list of lists of open problems in parameterized complexity.

3

CS Theory Toolkit by Prof. Ryan O'Donnell. Great for newbies, and includes interesting viewing angle on various topics: https://www.youtube.com/playlist?list=PLm3J0oaFux3ZYpFLwwrlv_EHH9wtH6pnX

3

100 exercises in the theory of automata and formal languages https://algomuse.net/ It's a kind of competition but problems are from research papers. Here http://www.openproblemgarden.org/ Some problems have hints. https://a3nm.net/work/research/questions/#other-lists-of-open-problems In this book, each chapter have some exercise: https://files....

3

From this question on cs.stackexchange, I became aware of the genus hierarchy of regular languages. Essentially, you can characterize regular languages based on the minimum genus surface in which the graph of their DFA may be embedded. It is shown in [1] that there exist languages of arbitrarily large genus and that this hierarchy is proper. Bonfante, ...

3

Algorithmic Game Theory Noam Nisan, Tim Roughgarden, Eva Tardos, Vijay V. Vazirani. Algorithmic Game Theory. Cambridge University Press, 24 de set. de 2007 History of Computer Science COOPER, S. Barry; VAN LEEUWEN, Jan (Ed.). Alan Turing: His work and impact. Elsevier, 2013. Learning theory Kearns, Michael J., Umesh Virkumar Vazirani, and Umesh Vazirani....

2

Parameterized complexity It might worth adding an answer since no one mentioned this area. A comprehensible, well written quite recent book is Parameterized Algorithms, M. Cygan et al., 2015 Another book is Parameterized complexity, R. Downey and M. Fellows, 1999 Meanwhile the former presents a comprehensible text about most of the used methods and ...

2

I like to introduce Vertex-Cover as a problem in which the underlying graph models a museum, so that the vertices represent the museum rooms and the edges represent the corridors. Then, it is easy for the students to understand that minimising the number of guards required to watch over the museum corresponds to finding a vertex cover. The guards are placed ...

2

There's the TLCA List of Open Problems, collecting unsolved problems in $\lambda$-calculi and related areas, such as proof theory, semantics and theory of programming languages. It is maintained by Ryu Hasegawa, Luca Paolini and Paweł Urzyczyn. There's also a related list, the RTA list of open problems, concerning rewriting theory. At some point it was ...

2

Technically it's an AI podcast but I love Lex Fridman's series: https://www.youtube.com/playlist?list=PLrAXtmErZgOdP_8GztsuKi9nrraNbKKp4 Theoretical CS does pop up in at least a few episodes.

1

I like very much the TCS+ series of online seminars: https://sites.google.com/site/plustcs/

1

In general, what is the relationship between time and space complexity classes? There are many unresolved questions such as: Is $PTIME = NLOGSPACE$? Is $PTIME = DLOGSPACE$? Is $PTIME = PSPACE$? Is $DSPACE(s(n)) \subseteq PTIME$ for some $s(n) = \omega(\log n)$? Is $DTIME(t(n)) \subseteq PSPACE$ for some super polynomial function $t(n)$? Also, there are ...

Only top voted, non community-wiki answers of a minimum length are eligible