Advertisement
Published in:
2008 | OriginalPaper | Chapter
Optimal Monotone Encodings
Authors : Noga Alon, Rani Hod
Published in: Automata, Languages and Programming
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Moran, Naor and Segev have asked what is the minimal
r
=
r
(
n
,
k
) for which there exists an (
n
,
k
)
-monotone encoding of length r
, i.e., a monotone injective function from subsets of size up to
k
of {1, 2, ...,
n
} to
r
bits. Monotone encodings are relevant to the study of tamper-proof data structures and arise also in the design of broadcast schemes in certain communication networks.
To answer this question, we develop a relaxation of
k
-superimposed families, which we call
α
-fraction
k
-multi-user tracing ((
k
,
α
)-FUT families). We show that
r
(
n
,
k
) =
Θ
(
k
log(
n
/
k
)) by proving tight asymptotic lower and upper bounds on the size of (
k
,
α
)-FUT families and by constructing an (
n
,
k
)-monotone encoding of length
O
(
k
log(
n
/
k
)).
We also present an explicit construction of an (
n
, 2)-monotone encoding of length 2log
n
+
O
(1), which is optimal up to an additive constant.