SAT-Based Search for Minwise Independent Families

作     者：Iurlano, Enrico Raidl, Günther R. 

作者机构：Algorithms and Complexity Group TU Wien Favoritenstraße 9-11/192-01 Vienna1040 Austria 

出 版 物：《arXiv》 (arXiv)

年 卷 期：2024年

核心收录：

主　　题：Group theory 

摘      要：Proposed for rapid document similarity estimation in web search engines, the celebrated property of minwise independence imposes highly symmetric constraints on a family F of permutations of {1, ..., n}: The property is fulfilled by F if for each j ∈ {1, ..., n}, any cardinality-j subset X ⊆ {1, ..., n}, and any fixed element x∗ ∈ X, it occurs with probability 1/j that a randomly drawn permutation π from F satisfies π(x∗) = min{π(x): x ∈ X}. The central interest is to find a family with fewest possible members meeting the stated constraints. We provide a framework that, firstly, is realized as a pure SAT model and, secondly, generalizes a heuristic of Mathon and van Trung to the search of these families. Originally, the latter enforces an underlying group-theoretic decomposition to achieve a significant speed-up for the computer-aided search of structures which can be identified with so-called rankwise independent families. We observe that this approach is suitable to find provenly optimal new representatives of minwise independent families while yielding a decisive speed-up, too. As the problem has a naive search space of size at least (n!)n, we also carefully address symmetry breaking. Finally, we add a bijective proof for a problem encountered by Bargachev when deriving a lower bound on the number of members in a minimal rankwise independent *** Codes 90C27, 68R05 © 2024, CC BY-SA.