András Salamon
  • Member for 11 years, 5 months
  • Last seen more than a week ago
What are the current best known upper and lower bounds on the (un)satisfiability threshold for random k-sat and/or 3-sat?
Accepted answer
19 votes

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 ...

View answer
Graph classes for which the diameter can be computed in linear time
Accepted answer
9 votes

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 ...

View answer
Hardness jumps in computational complexity?
21 votes

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 ...

View answer
How do database aggregations form a monoid?
Accepted answer
14 votes

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, ...

View answer
Constraint satisfaction problem (CSP) vs. satisfiability modulo theory (SMT); with a coda on constraint programming
51 votes

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 ...

View answer
Does Rabin/Yao exist (at least in a form that can be cited)?
Accepted answer
7 votes

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.)

View answer
CSPs with unbounded fractional hypertree width
Accepted answer
8 votes

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 ...

View answer
Reduction from independent set in hypergraphs to independent set in graphs
1 votes

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$ ...

View answer
What is the best exact algorithm to compute the core of a graph?
22 votes

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 ...

View answer
How many tautologies are there?
6 votes

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 ...

View answer
"All-different hypergraph coloring" - known problem?
8 votes

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 ...

View answer
What hierarchies and/or hierarchy theorems do you know?
9 votes

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 ...

View answer
Packing $n$ objects into $m$ bins whose size is variable
Accepted answer
2 votes

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$. ...

View answer
Fully linear time regular expression matching
Accepted answer
6 votes

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-...

View answer
Problems Between P and NPC
4 votes

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 ...

View answer
Can a hereditary graph class contain almost all, but not all, n-vertex graphs?
10 votes

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 ...

View answer
Evidence that UniqueSat is dense
Accepted answer
4 votes

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 ...

View answer
Lipton's most influential results
7 votes

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....

View answer
Complexity zoo for unary languages
Accepted answer
23 votes

There is no Zoo-style reference yet, but a recent automata-theoretic survey of Giovanni Pighizzini has been useful to me, especially the slides from his talk. Giovanni Pighizzini, Investigations on ...

View answer
Deterministic communication complexity vs partition number
7 votes

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
Research problems in communication complexity
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
Major unsolved problems in theoretical computer science?
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
Low space computation and branching program
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
Best current space lower bound for SAT?
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
The unreasonable power of non-uniformity
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
Planted Clique in G(n,p), varying p
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
Learnability of constraint satisfaction problems CSPs?
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
Major unsolved problems in theoretical computer science?
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
Gröbner bases in TCS?
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
Using Kolmogorov complexity as input "size"
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 ...

View answer