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$.)
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 ...
Simons Institute for the Theory of Computing:
Institute for Advanced Study:
Stanford Computer Science Theory:
100 exercises in the theory of automata and formal languages
It's a kind of competition but problems are from research papers.
Some problems have hints.
In this book, each chapter have some exercise:
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  that there exist languages of arbitrarily large genus and that this hierarchy is proper.
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.
Kearns, Michael J., Umesh Virkumar Vazirani, and Umesh Vazirani....
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 ...
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 ...
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 ...
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
Also, there are ...