5 papers
Linear Probing with Non-Greedy Insertions
Andrew Krapivin, William Kuszmaul, Jolyne Wang
Linear probing hash tables classically use a \emph{greedy} insertion strategy, placing a key in the first available position out of . If the h…
Toward Satisfiability Modulo Realizability
Andrew Krapivin, Benjamin Przybocki, Marijn J. H. Heule
Problems complete for the existential theory of the reals () arise throughout discrete geometry. We introduce satisfiability modulo realizability, a SAT-based a…
Near-Optimal Encodings of Cardinality Constraints
Andrew Krapivin, Benjamin Przybocki, Bernardo Subercaseaux
We present several novel encodings for cardinality constraints, which use fewer clauses than previous encodings and, more importantly, introduce new generally applicable techniques…
Optimal and Efficient Partite Decompositions of Hypergraphs
Andrew Krapivin, Benjamin Przybocki, Nicolás Sanhueza-Matamala +1
We study the problem of partitioning the edges of a -uniform hypergraph into a family of complete -partite hypergraphs (-cliques). We show that there is a partitio…
Optimal Bounds for Open Addressing Without Reordering
Martin Farach-Colton, Andrew Krapivin, William Kuszmaul
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…