2026-07-22T04:53:57Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:21060 2024-09-16T06:02:39Z ddc:004 open_access

Explicit and Near-Optimal Construction of t-Rankwise Independent Permutations Harvey, Nicholas Sahami, Arvin Rankwise independent permutations Letting t ≤ n, a family of permutations of [n] = {1,2,…, n} is called t-rankwise independent if for any t distinct entries in [n], when a permutation π is sampled uniformly at random from the family, the order of the t entries in π is uniform among the t! possibilities. Itoh et al. show a lower bound of (n/2)^⌊t/4⌋ for the number of members in such a family, and provide a construction of a t-rankwise independent permutation family of size n^O(t^2/ln(t)). We provide an explicit, deterministic construction of a t-rankwise independent family of size n^O(t) for arbitrary parameters t ≤ n. Our main ingredient is a way to make the elements of a t-independent family "more injective", which might be of independent interest. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Nicholas Harvey and Arvin Sahami 2024 Is Part Of LIPIcs, Volume 317, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX/RANDOM.2024.67 urn:nbn:de:0030-drops-210600 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2024.67 eng https://creativecommons.org/licenses/by/4.0/legalcode