Dimitris Achlioptas covers this in a survey article from the first edition of the Handbook of Satisfiability (PDF of draft). There is conjectured to be a single threshold $r_k$ for each $k \ge 3$, so ...

The eccentricity of a vertex $v$ is the length of a longest shortest path starting from $v$. The diameter is the maximal eccentricity over all vertices. Any BFS from a vertex will establish its ...

INDEPENDENT SET is NP-complete for (cross,triangle)-free graphs, but can be solved in linear time for (chair,triangle)-free graphs. (The X-free graphs are those that contain no graph from X as an ...

You ask why database aggregations have monoidal structure. Say we want to combine data values $a$ and $b$, but want to keep things general -- these may be integers, strings, floating point numbers, ...

SAT, CP, SMT, (much of) ASP all deal with the same set of combinatorial optimisation problems. However, they come at these problems from different angles and with different toolboxes. These ...

After more than two years, I have to assume the answer is "no". (Posting this stub answer so the question can be marked as answered.)

You linked to two papers, both with conjectures. I presume you mean Grohe's 2007 conjecture. This question was answered in 2008: Theorem 5. CSP(C$_0$,_) is in NP, but neither in P nor NP-complete ...

I am not as convinced as @Andrew Morgan is that this is "fair standard fare", and would also welcome pointers to a citable reduction. In particular, I do not see how to maintain a linear blowup if $k$ ...

Computing the core of a graph is hard: even deciding if a given 3-colourable graph is a core is co-NP-complete, see Hell and Nesetril. There are settings where core computation can be done ...

This is an extended comment to complement Ryan's answer, which deals with the thresholds where the number of clauses becomes large enough that the instance is almost surely unsatisfiable. One can also ...

A colouring in which every hyperedge is polychromatic (or rainbow) is also known as a strong colouring. Note that a strong colouring of a hypergraph is precisely a proper colouring of the Gaifman ...

Another strict hierarchy: branching programs which only test each bit a limited number of times. The more tests are allowed, the larger the class of branching programs. Usually the branching programs ...

One simple "bad" input that needs to be considered for worst-case analysis of this problem is as follows. Let $c=(\sqrt{17}-1)/2 \approx 1.56$. There are three objects of size $c$, $1$, and $1$. ...

Groz et al. explicitly state that the best known algorithm for general regular expressions (as of 2012) is $O(nm(\log\log n)/(\log n)^{3/2}+n+m)$, due to Bille and Thorup 2009, doi:10.1007/978-3-642-...

A problem that is not known to be either in FP or to be NP-hard is the problem of finding a minimal Steiner tree when the Steiner vertices are promised to fall on two straight line segments ...

To add to Daniel's answer, the precise density of hereditary classes has been extensively investigated in combinatorics. For a class $C$ of structures, the unlabelled slice $C_n$ is the set of ...

As far as I can tell, UniqueSAT is exponentially dense, in the sense that it contains $2^{\Omega(n)}$ instances of size $n$. (This is a stronger requirement than $2^{n^\varepsilon}$ for infinitely ...

Multiparty communication complexity and the Number-on-Forehead model were introduced by Ashok K. Chandra, Merrick L. Furst and Richard J. Lipton in Multi-party Protocols, STOC 1983, doi:10.1145/800061....

You remark that lower bounds on $Pn(f)$ are closely related to all existing lower bound techniques. For Boolean functions this seems to be true, as long as the log-rank conjecture is true. However, $... View answer 6 votes Several long-standing key open problems are in the Kushilevitz and Nisan textbook (see also the list of errata which mentions that Open Problem 8.6 was solved by Dietzfelbinger). Razborov's 2011 ... View answer 147 votes Can multiplication of$n$by$n$matrices be done in$O(n^2)$operations? The exponent of the best known upper bound even has a special symbol,$\omega$. Currently$\omega$is approximately 2.376, by ... View answer 2 votes Denoting the class of functions computed by branching programs of size$f(n)$by$\text{BP}(f)$, the best known bound seems to be the trivial$\text{DSPACE}(S(n)) \subseteq \text{BP}(2^{O(S(n))})$. ... View answer Accepted answer 3 votes Looks like the best bound known (for multitape Turing machines) is logarithmic. Suppose$\delta\log n$bits of binary worktape is enough to decide whether any$n$-bit CNF formula is satisfiable, for ... View answer 10 votes For me, the starkest illustration of the power of non-uniformity is that a suitably padded version of the Halting Problem is already in P/1. A single bit of advice is then enough to decide this ... View answer Accepted answer 9 votes If$p$is constant, then the size of the maximum clique in the$G(n,p)$model is almost everywhere a constant multiple of$\log n$, with the constant proportional to$\log (1/p)$. (See Bollobás, p.... View answer 6 votes You are probably looking for this paper: Víctor Dalmau and Peter Jeavons, Learnability of quantified formulas, TCS 306 485–511, 2003. doi:10.1016/S0304-3975(03)00342-6 In short, the learning ... View answer 1 votes Conjunctive query containment over bag semantics In a GoogleFight between two search queries, can one tell if the first query always wins, without looking at the data? This 1993 question from ... View answer 12 votes Gröbner bases have been applied to constraint satisfaction problems (see this grant). At this point Gröbner basis techniques do not appear to be useful for the applications of constraint satisfaction,... View answer 4 votes An easy case seems to be where the language$S$contains only padded instances. When$S$is obtained from a language$L$by padding each instance of size$n$with$2^n-n$symbols,$f^K_{n}\$ can be in ...