We present several novel encodings for cardinality constraints, which use fewer clauses than previous encodings and, more importantly, introduce new generally applicable techniques for constructing compact encodings. First, we present a CNF encoding for the AtMostOne(x_1,…,x_n) constraint using 2n + 2 √{2n} + O(∛n) clauses, thus refuting the conjectured optimality of Chen’s product encoding. Our construction also yields a smaller monotone circuit for the threshold-2 function, improving on a 50-year-old construction of Adleman and incidentally solving a long-standing open problem in circuit complexity. On the other hand, we show that any encoding for this constraint requires at least 2n + √{n+1} - 2 clauses, which is the first nontrivial unconditional lower bound for this constraint and answers a question of Kučera, Savický, and Vorel. We then turn our attention to encodings of AtMost_k(x_1,…,x_n), where we introduce grid compression, a technique inspired by hash tables, to give encodings using 2n + o(n) clauses as long as k = o(∛{n}) and 4n + o(n) clauses as long as k = o(n). Previously, the smallest known encodings were of size (k+1)n + o(n) for k ≤ 5 and 7n - o(n) for k ≥ 6.

In a widely-cited 1985 result, Yao showed that any greedy open-addressed hash table, when filled to 1 − є full, must incur an amortized expected query time of at least Ω(logє−1). To overcome this lower bound, prior work has focused on modifying the setup of the insertion algorithm, by either reordering items or placing items non-greedily. We show that, in fact, no such modifications are necessary: by simply decoupling the greedy query algorithm from the greedy insertion algorithm, it is possible to get an amortized expected query time of O(1). The same relaxation also lets us bypass a barrier for worst-case expected query time, bringing the bound down to O(logє−1). Finally, we show how to achieve both of these query bounds while also achieving near-optimal insertion times, for both solutions that do and solutions that do not know the parameter є beforehand.

We study the problem of partitioning the edges of a d-uniform hypergraph H into a family F of complete d-partite hypergraphs (d-cliques). We show that there is a partition F in which every vertex v ∈ V(H) belongs to at most (1/d! + od(1))nd−1/lgn members of F. This settles the central question of a line of research initiated by Erdős and Pyber (1997) for graphs, and more recently by Csirmaz, Ligeti, and Tardos (2014) for hypergraphs. The d=2 case of this theorem answers a 40-year-old question of Chung, Erdős, and Spencer (1983). An immediate corollary of our result is an improved upper bound for the maximum share size for binary secret sharing schemes on uniform hypergraphs.

In this paper, we revisit one of the simplest problems in data structures: the task of inserting elements into an open-addressed hash table so that elements can later be retrieved with as few probes as possible. We show that, even without reordering elements over time, it is possible to construct a hash table that achieves far better expected search complexities (both amortized and worst-case) than were previously thought possible. Along the way, we disprove the central conjecture left by Yao in his seminal paper “Uniform Hashing is Optimal”.