3 papers
cs.CC2026
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…
math.CO2025
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…
cs.DS2025
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…