DROPS

Document

RANDOM

DOI: 10.4230/LIPIcs.APPROX/RANDOM.2024.67

Explicit and Near-Optimal Construction of t-Rankwise Independent Permutations

Authors: Nicholas Harvey and Arvin Sahami

Published in: LIPIcs, Volume 317, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)

Abstract

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.

Cite as

Nicholas Harvey and Arvin Sahami. Explicit and Near-Optimal Construction of t-Rankwise Independent Permutations. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 317, pp. 67:1-67:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{harvey_et_al:LIPIcs.APPROX/RANDOM.2024.67,
  author =	{Harvey, Nicholas and Sahami, Arvin},
  title =	{{Explicit and Near-Optimal Construction of t-Rankwise Independent Permutations}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)},
  pages =	{67:1--67:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-348-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{317},
  editor =	{Kumar, Amit and Ron-Zewi, Noga},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2024.67},
  URN =		{urn:nbn:de:0030-drops-210600},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2024.67},
  annote =	{Keywords: Rankwise independent permutations}
}

Search Results

Documents authored by Harvey, Nicholas

Explicit and Near-Optimal Construction of t-Rankwise Independent Permutations

Abstract

Cite as

Thanks for your feedback!

Could not send message