Narrow Results

Network operation may require that a specified number k of nodes be able to communicate via paths consisting of operating edges and nodes. In an environment of node and edge failure, this leads to associated reliability measures. When the k nodes are known in advance, this has been widely studied as k-terminal reliability; when the k nodes are chosen uniformly at random, this has been studied as k-resilience. A third notion, when it suffices to have anyk nodes communicate, is related to the expected size of the largest component in the network. We generalize these three measures to the probability that given h nodes chosen in advance and i nodes chosen at random, they appear in a component of size at least k = h + i + j. As expected, for general networks, for most choices of (h, i, j) the computation is #P-complete and hence unlikely to admit a polynomial time algorithm. We develop polynomial time algorithms in the special case that the network is series-parallel, which subsume and generalize earlier methods for k-terminal reliability and k-resilience.

Numerous constructions of the best known covering arrays are effective only for specific numbers of symbols. Fusion replaces numerous symbols by one, and can thereby employ such constructions to produce useful covering arrays on fewer symbols. Augmentation instead replaces one symbol by many, permitting the construction of covering arrays from those with fewer symbols. Until this time, augmentation has been of limited value because it introduces substantial redundant coverage. Here a general augmentation method is improved upon by analyzing the classes of interactions to be covered and employing variants of covering arrays, quilting arrays, to reduce the redundancy introduced. For strengths four, five, and six, quilting arrays are produced that can be used in the refined augmentation to produce many best known covering arrays.

Covering arrays are combinatorial objects that have been successfully applied in design of test suites for testing systems such as software, hardware, and networks where failures can be caused by the interaction between their parameters. Let $n$ and $k$ be positive integers with $k\ge 3$. Two vectors $x\in {\mathbb{Z}}_{g_1}^n$ and $y\in {\mathbb{Z}}_{g_2}^n$ are qualitatively independent if for any ordered pair $(a,b)\in {\mathbb{Z}}_{g_1}\times {\mathbb{Z}}_{g_2}$, there exists an index $j\in \{0,1,\dots ,n-1\}$ such that $(x(j),y(j))=(a,b)$. Let $G$ be a graph with $k$ vertices $v_1,v_2,\dots ,v_k$ with respective vertex weights $g_1,g_2,\dots ,g_k$. A mixed covering array on$G$, denoted by $\mathrm{\text{CA}}(n,G,{\prod }_{i=1}^k{g}_i)$, is a $k\times n$ array such that row $i$ corresponds to vertex $v_i$, entries in row $i$ are from $Z_{g_i}$; and if $\{v_x,v_y\}$ is an edge in $G$, then the rows $x,y$ are qualitatively independent. The parameter $n$ is the size of the array. Given a weighted graph $G$, a mixed covering array on $G$ with minimum size is optimal. In this paper, we introduce some basic graph operations to provide constructions for optimal mixed covering arrays on the family of graphs with treewidth at most three.

Capacitance-coupling and mutual inductance between the neighboring wires of global interconnects give rise to crosstalk effects, which are one of the biggest signal integrity problems in DSM circuits today. Previous models for crosstalk-induced faults assume that all the wires of a bus act together to induce crosstalk effects on a single wire. Based on recent simulation results of Sirisaengtaksin and Gupta, we use a more general model of crosstalk-induced faults that allows tradeoffs between efficiency of tests and quality of tests. We construct provably optimal test patterns that covers all crosstalk-induced faults under this general model. Our test patterns admit simple generators for at-speed testing in BIST. The test methodology proposed here can result in huge savings in test cost. In particular, the required linear number of test patterns can be reduced to a constant number of test patterns by accepting only a few percent of error, thus allowing our test methodology to scale with bus width and technology.

A perfect hash family𝖯𝖧𝖥(N; k, v, t) is an N × k array on v symbols with v ≥ t, in which in every N × t subarray, at least one row is comprised of distinct symbols. Perfect hash families have a wide range of applications in cryptography, particularly to secure frameproof codes, in database management, and are indirectly used in software interaction testing. A simple one-row-at-a-time greedy algorithm for constructing small perfect hash families is described. The algorithm is deterministic, and its worst-case runtime is polynomial in k and v but exponential in t; consequently, when t is fixed, the algorithm runs in polynomial time in the worst case. It provides a deterministic guarantee that the number N of rows produced is O(log k). In addition to these strong asymptotic guarantees, the method is shown to be practical for the computation of perfect hash families for "small" values of k and t.