Improved bounds for separating hash families

An ${(N;n,m,\{w_1,\ldots, w_t\})}$ -separating hash family is a set ${\mathcal{H}}$ of N functions ${h: \; X \longrightarrow Y}$ with ${|X|=n, |Y|=m, t \geq 2}$ having the following property. For any pairwise disjoint subsets ${C_1, \ldots, C_t \subseteq X}$ with ${|C_i|=w_i, i=1, \ldots, t}$ , there exists at least one function ${h \in \mathcal{H}}$ such that ${h(C_1), h(C_2), \ldots, h(C_t)}$ are pairwise disjoint. Separating hash families generalize many known combinatorial structures such as perfect hash families, frameproof codes, secure frameproof codes, identifiable parent property codes. In this paper we present new upper bounds on n which improve many previously known bounds. Further we include constructions showing that some of these bounds are tight.     

Constructions and bounds for separating hash families

In this paper, we present a new construction for strong separating hash families by using hypergraphs and obtain some optimal separating hash families. We also improve some previously known bounds of separating hash families.     

Bounds for separating hash families

This paper aims to present new upper bounds on the size of separating hash families. These bounds improve previously known bounds for separating hash families.     

On generalized separating hash families

Separating hash families are useful combinatorial structures which are studied in a general form in this paper. Necessary and sufficient conditions for the existence of certain types of generalized hash functions are considered.     

A bound on the size of separating hash families

The paper provides an upper bound on the size of a (generalized) separating hash family, a notion introduced by Stinson, Wei and Chen. The upper bound generalizes and unifies several previously known bounds which apply in special cases, namely bounds on perfect hash families, frameproof codes, secure frameproof codes and separating hash families of small type.     

Some recursive constructions for perfect hash families

An (n, m, w)-perfect hash family is a set of functions F such that for each f ϵ F, and for any X ⊆ {1,…,n} such that |X| = w, there exists at least one f ϵ F such that f|_x is one-to-one. Perfect hash families have been extensively studied by computer scientists for over 15 years, mainly due to their applications in database management. In particular, much attention has been given to finding efficient algorithms to construct perfect hash families. In this article, we study perfect hash families from a combinatorial viewpoint, and describe some new recursive constructions for these objects. © 1996 John Wiley & Sons, Inc.     

A tight bound for frameproof codes viewed in terms of separating hash families

Frameproof codes have been introduced for use in digital fingerprinting that prevent a coalition of \(w\) or fewer legitimate users from constructing a fingerprint of another user not in the coalition. It turns out that \(w\) -frameproof codes are equivalent to separating hash families of type \(\{1,w\}\) . In this paper we prove a tight bound for frameproof codes in terms of separating hash families.     

Explicit constructions of separating hash families from algebraic curves over finite fields

Let X be a set of order n and Y be a set of order m. An (n,m,{w ₁, w ₂})-separating hash family is a set of N functions from X to Y such that for any with , |X ₁| = w ₁ and |X ₂| = w ₂, there exists an element such that . In this paper, we provide explicit constructions of separating hash families using algebraic curves over finite fields. In particular, applying the Garcia–Stichtenoth curves, we obtain an infinite class of explicitly constructed (n,m,{w ₁,w ₂})–separating hash families with for fixed m, w ₁, and w ₂. Similar results for strong separating hash families are also obtained. As consequences of our main results, we present explicit constructions of infinite classes of frameproof codes, secure frameproof codes and identifiable parent property codes with length where n is the size of the codes. In fact, all the above explicit constructions of hash families and codes provide the best asymptotic behavior achieving the bound , which substantially improve the results in [ 8, 15, 17] give an answer to the fifth open problem presented in [11].     

Constructions of 2‐cover‐free families and related separating hash families

Cover‐free families (CFFs) were considered from different subjects by numerous researchers. In this article, we mainly consider explicit constructions of (2; d)‐cover‐free families. We also determine the size of optimal 2‐cover‐free‐families on 9, 10, and 11 points. Related separating hash families, which can be used to construct CFFs, are also discussed. © 2006 Wiley Periodicals, Inc. J Combin Designs 14: 423–440, 2006     

Some upper bounds for density of function spaces

Let Cα(X,Y) be the set of all continuous functions from X to Y endowed with the set-open topology where α is a hereditarily closed, compact network on X which is closed under finite unions. We proved that the density of the space Cα(X,Y) is at most iw(X)⋅d(Y) where iw(X) denotes the i-weight of the Tychonoff space X, and d(Y) denotes the density of the space Y when Y is an equiconnected space with equiconnecting function Ψ, and Y has a base consists of Ψ-convex subsets of Y. We also prove that the equiconnectedness of the space Y cannot be replaced with pathwise connectedness of Y. In fact, it is shown that for each infinite cardinal κ, there is a pathwise connected space Y such that π-weight of Y is κ, but Souslin number of the space Ck([0,1],Y) is κ².     

Explicit constructions for perfect hash families

Let k, v, t be integers such that k ≥ v ≥ t ≥ 2. A perfect hash family (N; k, v, t) can be defined as an N × k array with entries from a set of v symbols such that every N × t subarray contains at least one row having distinct symbols. Perfect hash families have been studied by over 20 years and they find a wide range of applications in computer sciences and in cryptography. In this paper we focus on explicit constructions for perfect hash families using combinatorial methods. We present many recursive constructions which result in a large number of improved parameters for perfect hash families. The paper also includes extensive tables for parameters with t = 3, 4, 5, 6 of newly constructed perfect hash families.      

Some upper bounds for the diameters of convex polytopes

Δ(d, n) is defined to be the maximum diameter of ad-polytope withn-facets. The main results of the work are an evaluation of Δ(4, 10) and Δ(5, 11). Also, improved upper bounds are found for Δ(6, 13) and Δ(7,14).     

Some upper and lower bounds on PSD-rank

Positive semidefinite rank (PSD-rank) is a relatively new complexity measure on matrices, with applications to combinatorial optimization and communication complexity. We first study several basic properties of PSD-rank, and then develop new techniques for showing lower bounds on the PSD-rank. All of these bounds are based on viewing a positive semidefinite factorization of a matrix M as a quantum communication protocol. These lower bounds depend on the entries of the matrix and not only on its support (the zero/nonzero pattern), overcoming a limitation of some previous techniques. We compare these new lower bounds with known bounds, and give examples where the new ones are better. As an application we determine the PSD-rank of (approximations of) some common matrices.     

Some inequalities involving upper bounds for some matrix operators I

In this paper we consider the problem of finding upper bounds of certain matrix operators such as Hausdorff, Nörlund matrix, weighted mean and summability on sequence spaces l _p(w) and Lorentz sequence spaces d(w, p), which was recently considered in [9] and [10] and similarly to [14] by Josip Pecaric, Ivan Peric and Rajko Roki. Also, this study is an extension of some works by G. Bennett on l _p spaces, see [1] and [2].     

On subset-resilient hash function families

Designs, Codes and Cryptography - In this paper, we analyze the security of subset-resilient hash function families, which is first proposed as a requirement of a hash-based signature scheme called...     

Some upper bounds for sums of eigenvalues of the Neumann Laplacian

Let be the th Neumann eigenvalue of a bounded domain with piecewisely smooth boundary in . In 1992, P. Kröger proved that , where the upper bound is sharp in view of Weyl's asymptotic formula. The aim of this paper is twofold. First, we will improve this estimate by multiplying a factor in terms of to its right-hand side which approaches strictly from below to 1 as tends to infinity. Second, we will generalize Kröger's estimate to the case when is a compact Euclidean submanifold.

     

Strengthening hash families and compressive sensing

The deterministic construction of measurement matrices for compressive sensing is a challenging problem, for which a number of combinatorial techniques have been developed. One of them employs a widely used column replacement technique based on hash families. It is effective at producing larger measurement matrices from smaller ones, but it can only preserve the strength (level of sparsity supported), not increase it. Column replacement is extended here to produce measurement matrices with larger strength from ingredient arrays with smaller strength. To do this, a new type of hash family, called a strengthening hash family, is introduced. Using these hash families, column replacement is shown to increase strength under two standard notions of recoverability. Then techniques to construct strengthening hash families, both probabilistically and deterministically, are developed. Using a variant of the Stein–Lovász–Johnson theorem, a deterministic, polynomial time algorithm for constructing a strengthening hash family of fixed strength is derived.     

Linear hash families and forbidden configurations

The classical orthogonal arrays over the finite field underlie a powerful construction of perfect hash families. By forbidding certain sets of configurations from arising in these orthogonal arrays, this construction yields previously unknown perfect, separating, and distributing hash families. When the strength s of the orthogonal array, the strength t of the hash family, and the number of its rows are all specified, the forbidden sets of configurations can be determined explicitly. Each forbidden set leads to a set of equations that must simultaneously hold. Hence computational techniques can be used to determine sufficient conditions for a perfect, separating, and distributing hash family to exist. In this paper the forbidden configurations, resulting equations, and existence results are determined when (s, t) ∈ {(2, 5), (2, 6), (3, 4), (4, 3)}. Applications to the existence of covering arrays of strength at most six are presented.      

Lower bounds and upper bounds for chromatic polynomials

In this paper we give lower bounds and upper bounds for chromatic polynomials of simple undirected graphs on n vertices having m edges and girth exceeding g © 1993 John Wiley & Sons, Inc.