Linear time Constructions of some d-Restriction Problems

2014/06/09 by Nader H. Bshouty, Bshouty, Nader H. · 2 citations
Computer Science · #Complexity and Algorithms in Graphs #Cryptography and Data Security #Advanced Graph Theory Research

paper · pdf · doi:10.48550/arxiv.1406.2108

Abstract

We give new linear time globally explicit constructions for perfect hash families, cover-free families and separating hash functions.

Cited by

• A Fast Binary Splitting Approach for Non-Adaptive Learning of Erdős--Rényi Graphs
• Non-Adaptive Learning a Hidden Hipergraph

Related

• Perfect and separating Hash families: new bounds via the algorithmic\n cluster expansion local lemma
• Discrete Temporal Constraint Satisfaction Problems
• Constructions and bounds for separating hash families
• Bounds on k-hash distances and rates of linear codes
• On the k-Independence Required by Linear Probing and Minwise\n Independence