2017/03/15 by Shagnik Das, Tamás Mészáros, Das, Shagnik +1
Computer Science · Engineering · #Algorithms and Data Compression #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #VLSI and Analog Circuit Testing #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.1703.05252
openalex publication_date 2017/03/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Given a set S of v ≥ 2 symbols, and integers k ≥ t ≥ 2 and N ≥ 1, an N × k array A ∈ SN × k is an (N; t, k, v)-covering array if all sequences in St appear as rows in every N × t subarray of A. These arrays have a wide variety of applications, driving the search for small covering arrays. The covering array number, CAN(t,k,v), is the smallest N for which an (N; t,k,v)-covering array exists. In this paper, we combine probabilistic and linear algebraic constructions to improve the upper bounds on CAN(t,k,v) by a factor of ln v, showing that for prime powers v, CAN(t,k,v) ≤ (1 + o(1)) ( (t-1) vt / (2 log2 v - log2 (v+1)) )log2 k, which also offers improvements for large v that are not prime powers. Our main tool, which may be of independent interest, is a construction of an array with vt rows that covers the maximum possible number of subsets of size t.