Marvin Künnemann

Timo Fritsch, Marvin Künnemann, Mirza Redzic et al.

Consider the fundamental task of finding independent sets of (constant) size $k$ in a given $n$-node hypergraph. How is the time complexity affected by the sparsity of the input, i.e., the number of hyperedges $m$? Turán's theorem implies that the problem is trivial if $m=O(n^{2-ε})$ for some $ε> 0$. Above that threshold (i.e., if $m=Θ(n^γ)$ for some $γ\ge 2$), we give a perhaps surprising algorithm with running time $O\left(\min\left\{n^{\fracω{3}k} + m^{k/3}, n^k\right\}\right)$ (for $k$ divisible by 3), which is essentially conditionally optimal for all $γ\ge 2$, assuming the $k$-clique and 3-uniform hyperclique hypotheses (here, $ω<2.372$ denotes the matrix multiplication exponent). In fact, we obtain a more detailed time complexity, sensitive to the arity distribution of the hyperedges. To study such phenomena in more generality, we study the time complexity of finding solutions of (constant) size $k$ in sparse instances of Boolean constraint satisfaction problems, where $n$ and $m$ denote the number of variables and constraints. Our results include an essentially full classification of the influence of sparsity for Boolean constraint families of binary arity. Of particular technical interest is a conditionally tight algorithm for the family consisting of the binary NAND and Implication constraints, with a running time of $Θ(m^{ωk/6 \pm c})$. Further, we identify a large class of constraint families $F$ that exhibits a sharp phase transition: there is a threshold $γ_F$ such that the problem is trivial for $m=O(n^{γ_F-ε})$, but requires essentially brute-force running time $Θ(n^{k\pm c})$ for $m=Ω(n^{γ_F})$, assuming the 3-uniform hyperclique hypothesis. Notably, in many cases the combination of constraints display higher time complexity than either constraint alone.

Nick Fischer, Marvin Künnemann, Mirza Redžić et al.

Is detecting a $k$-clique in $k$-partite regular (hyper-)graphs as hard as in the general case? Intuition suggests yes, but proving this -- especially for hypergraphs -- poses notable challenges. Concretely, we consider a strong notion of regularity in $h$-uniform hypergraphs, where we essentially require that any subset of at most $h-1$ is incident to a uniform number of hyperedges. Such notions are studied intensively in the combinatorial block design literature. We show that any $f(k)n^{g(k)}$-time algorithm for detecting $k$-cliques in such graphs transfers to an $f'(k)n^{g(k)}$-time algorithm for the general case, establishing a fine-grained equivalence between the $h$-uniform hyperclique hypothesis and its natural regular analogue. Equipped with this regularization result, we then fully resolve the fine-grained complexity of optimizing Boolean constraint satisfaction problems over assignments with $k$ non-zeros. Our characterization depends on the maximum degree $d$ of a constraint function. Specifically, if $d\le 1$, we obtain a linear-time solvable problem, if $d=2$, the time complexity is essentially equivalent to $k$-clique detection, and if $d\ge 3$ the problem requires exhaustive-search time under the 3-uniform hyperclique hypothesis. To obtain our hardness results, the regularization result plays a crucial role, enabling a very convenient approach when applied carefully. We believe that our regularization result will find further applications in the future.

Amir Abboud, Arturs Backurs, Karl Bringmann et al.

To handle vast amounts of data, it is natural and popular to compress vectors and matrices. When we compress a vector from size $N$ down to size $n \ll N$, it certainly makes it easier to store and transmit efficiently, but does it also make it easier to process? In this paper we consider lossless compression schemes, and ask if we can run our computations on the compressed data as efficiently as if the original data was that small. That is, if an operation has time complexity $T(\rm{inputsize})$, can we perform it on the compressed representation in time $T(n)$ rather than $T(N)$? We consider the most basic linear algebra operations: inner product, matrix-vector multiplication, and matrix multiplication. In particular, given two compressed vectors, can we compute their inner product in time $O(n)$? Or perhaps we must decompress first and then multiply, spending $Ω(N)$ time? The answer depends on the compression scheme. While for simple ones such as Run-Length-Encoding (RLE) the inner product can be done in $O(n)$ time, we prove that this is impossible for compressions from a richer class: essentially $n^2$ or even larger runtimes are needed in the worst case (under complexity assumptions). This is the class of grammar-compressions containing most popular methods such as the Lempel-Ziv family. These schemes are more compressing than the simple RLE, but alas, we prove that performing computations on them is much harder.

Benjamin Doerr, Marvin Künnemann

The cryptogenography problem, introduced by Brody, Jakobsen, Scheder, and Winkler (ITCS 2014), is to collaboratively leak a piece of information known to only one member of a group (i)~without revealing who was the origin of this information and (ii)~without any private communication, neither during the process nor before. Despite several deep structural results, even the smallest case of leaking one bit of information present at one of two players is not well understood. Brody et al.\ gave a 2-round protocol enabling the two players to succeed with probability $1/3$ and showed the hardness result that no protocol can give a success probability of more than~$3/8$. In this work, we show that neither bound is tight. Our new hardness result, obtained by a different application of the concavity method used also in the previous work, states that a success probability better than 0.3672 is not possible. Using both theoretical and numerical approaches, we improve the lower bound to $0.3384$, that is, give a protocol leading to this success probability. To ease the design of new protocols, we prove an equivalent formulation of the cryptogenography problem as solitaire vector splitting game. Via an automated game tree search, we find good strategies for this game. We then translate the splits that occurred in this strategy into inequalities relating position values and use an LP solver to find an optimal solution for these inequalities. This gives slightly better game values, but more importantly, it gives a more compact representation of the protocol and a way to easily verify the claimed quality of the protocol. These improved bounds, as well as the large sizes and depths of the improved protocols we find, suggests that finding good protocols for the cryptogenography problem as well as understanding their structure are harder than what the simple problem formulation suggests.