30 problems

The Exponential Time Hypothesis (ETH) is the hypothesis that $3$-SAT has no deterministic algorithm with running time subexponential in the number of variables. ETH. $3$-SAT admits…

The iterated logarithm function is defined recursively by … For a positive integer $k$, $k$-SAT asks whether a Boolean formula with $n$ variables has a satisfying assignment. Stron…

Let $\gamma>0$ be a positive real number. In the word RAM model with word size $O(\log n)$ bits, consider algorithms deciding whether a graph with $m$ edges contains a triangle. Tr…

Strong Exponential-Time Hypothesis. No such algorithmic shortcuts exist for the general, unrestricted $K$-SAT problem.

The randomized Exponential Time Hypothesis (rETH) is the hypothesis that $3$-SAT has no randomized algorithm with running time subexponential in the number of variables and success…

The 3SUM problem asks whether, given $n$ integers from $\{-n^4,\ldots,+n^4\}$, there is a triple satisfying the 3SUM condition. 3SUM conjecture. The 3SUM problem on $n$ such intege…

The Triangle Detection problem asks whether an $n$-node graph contains a triangle. A strongly subcubic combinatorial algorithm is a combinatorial algorithm whose running time is…

The strong exponential time hypothesis concerns Boolean satisfiability. For an integer $k\geq 3$, let ${\sc k\text{-Sat}}$ denote the problem of deciding satisfiability of Boolean…

Kernel matrices may be applied to arbitrary vectors, including vectors with both positive and negative coordinates. Nearly quadratic-time conjecture. The arbitrary-vector case may…

Let $G=(V,E,w)$ be a directed graph with integer edge weights in $[-M,M]$ and no negative cycles, or an undirected graph with integer edge weights in $[0,M]$. The all-pairs-shortes…

Combinatorial triangle-detection conjecture. There is no $O(n^{3-\eps})$-time combinatorial algorithm for finding a triangle in an undirected graph.

Combinatorial triangle-detection conjecture. There is no $O(n^{3-\eps})$-time combinatorial algorithm for finding a triangle in an undirected graph.

Let $q$-CNFSAT denote the satisfiability problem for conjunctive normal form formulas whose clauses have at most $q$ literals, and let $n$ be the number of variables in the input f…

8-profile hardness conjecture. In direct analogy with the case of $\mathbb{S}_4$, these occurrences constitute the “hard case” for computing the $8$-profile.

For positive integers $n$ and $m$, let $\emph{\textsf{OV}}(n,m)$ denote the Orthogonal Vectors problem: given sets $A=\{x^{(1)},\ldots,x^{(n)}\}$ and…

Let $k>r\geq 3$ and let an $r$-uniform hypergraph be a hypergraph whose edges have size $r$. A $k$-hyperclique is a set of $k$ vertices such that every $r$-subset is an edge. The L…

In the $(k,N,r)$-SUM problem, the input consists of $r$ elements $z_1,\ldots,z_r$, independently and uniformly chosen from $\{-N,\ldots,N\}$. The goal is to find an ordered $k$-tup…

For parameters $k=O(1)$ and $r$, the $k$-SUM problem gives a list of $r$ numbers and asks for $k$ of them whose sum is zero, assuming a solution exists. A sort-and-match algorithm…

A planar graph is a graph that can be drawn in the plane without crossing edges, and the diameter problem asks for the maximum distance between two vertices of a planar graph. A qu…

Let sparse graphs have $m=\tilde{O}(n)$ edges, and consider the four variants obtained by choosing directed or undirected graphs and weighted or unweighted edges. For…

Given a set $S$ of integers, let $n=|S|$. The 3SUM problem asks whether there are three integers $a,b,c\in S$ such that $a+b=c$. 3SUM Conjecture. Every algorithm solving 3SUM takes…

Let $\ell$ be an integer, and let $G$ be an $\ell$-layered directed acyclic graph with layers $L_1,\ldots,L_\ell$, where every edge goes from $L_i$ to $L_{i+1}$. An $\ell$-layered…

Consider the word-RAM model of computation with word length $O(\log b)$ for inputs of length $b$. An undirected graph $G$ has $m$ edges. Triangle Conjecture. There exists a constan…

Let 3-SAT be the satisfiability problem for Boolean formulas in conjunctive normal form whose clauses have at most three literals. A problem is solvable in subexponential time if,…

Strong worst-case clique-counting hardness conjecture. Any randomized algorithm $A$ for \textsc{\#(k,s)-clique} with error probability less than $1/3$ takes time…