11 problems

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…

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…

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…

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

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…

Let $G$ be an input graph with $n$ vertices and $m$ edges. An algorithm runs in the word RAM model with word size $O(\log n)$ bits. Triangle Detection Conjecture. There exists…

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…

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…