8
The famous graph (the complement of the disjoint union of $n/3$ triangles) with $3^{n/3}$ maximal cliques is $K_1 \cup K_2$-free, and thus has none of $2C_4$, $C_5$, $P_5$ as an induced subgraph.
https://doi.org/10.1007/BF02760024
4
For arbitrarily large number $n$ of variables, the following CNF formula $\phi$ is not satisfiable, has only three clauses, and a $2K_2$-free clause-variable incidence graph:
$C_1=(x_1)$, $C_2=(\neg x_1)$, $C_3=(x_1,\ldots,x_n)$.
Thus, to get more interesting lower bounds one needs to make assumption about the minimum clause size or about the size of classes ...
3
I stumbled upon this question now, many years later. In the interim the following paper has appeared:
https://dl.acm.org/doi/10.1145/3278158
https://arxiv.org/abs/1704.08705
There the authors do precisely what Kaveh asks for in his question 2: they give a (uniform) TC0 algorithm for balancing, hence obtaining an alternative proof of the main result in Buss '...
2
There are models of how to compute with arbitrary chemical reactions using molecules that drift around and randomly collide. They crop up in parallel computing models sometimes. It's probably not what you're looking for, but it might be interesting to learn about.
For an example, the ambient calculus. The process calculus wikipedia page includes some others.
2
A more recent open list of problems can be seen in the open problem session videos of the 2019 Workshop on Kernelization (WorKer 2019) (Session 1, Session 2).
Several of the problems mentioned already remain open:
Directed Feedback Vertex Set and Planar Vertex Deletion parameterized
by the number $k$ of vertex deletions as mentioned by Bart remain
open.
The ...
Only top voted, non community-wiki answers of a minimum length are eligible
