Skip to main content
11 votes

Lower-bounds under SETH

Most problems need at least linear time, so $O(n \log n)$ may be a little too close to optimal for a SETH based lower bound, generally we want running times where one can improve on the exponent by ...
Ryan Williams's user avatar
8 votes
Accepted

Reference request: complexity of $k$-partite $k$-SAT

Claim: If there exists an $\epsilon > 0$ such that for every $k'$, $k'$-partite $k'$-SAT can be solved in $2^{n(1-\epsilon)}$ time, then SETH fails. Proof: Suppose such an algorithm exists. We ...
daniello's user avatar
  • 3,266
8 votes
Accepted

Relation between ACC^0 and DTIME

Most people would believe that DTIME(n) contains problems that are not in non-uniform ACC^0 (poly size). One reason is that the containment of DTIME(n) in non-uniform ACC^0 implies P is contained in ...
Ryan Williams's user avatar
6 votes
Accepted

The problem of deciding whether a monotone CNF implies a monotone DNF

Assuming SETH, the problem is not solvable in time $O\bigl(2^{(1-\epsilon)n}\mathrm{poly}(l)\bigr)$ for any $\epsilon>0$. First, let me show that this is true for the more general problem where $\...
Emil Jeřábek's user avatar
4 votes
Accepted

Hardness of Subgraph isomorphism problem for sparse pattern graph

It is $W[1]$-hard even when $G$ has maximum degree $3$, but $FPT$ if $G$ has constant treewidth (all the above examples have constant treewidth). See the paper Everything you always wanted to know ...
daniello's user avatar
  • 3,266
3 votes

Solving All-Pairs Shortest Paths using a distance matrix in sub-cubic time

The discussion in this paper, Section 3 beginning on page 7, might be useful to you. It focuses on reducing distance product witnesses to distance product, which is the same as distance vs path APSP ...
GMB's user avatar
  • 2,403
2 votes

Algorithms in preprocessed universe

As Ricky Demer said in his comment, many search problems can be sped up with sorting or building some other index structure Lowest common ancestor queries can be answered in constant time with linear ...
adrianN's user avatar
  • 877

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