A double-change covering design (dccd) is an ordered set of blocks with block size k is an ordered collection of b blocks, B = {B1,B2, · · · ,Bb}, each an unordered subset of k distinct elements from [v] = {1, 2, · · · , v}, which obey: (1) each block differs from the previous block by two elements, and, (2) every unordered pair of [v] appears in at least one block. The object is to minimize b for a fixed v and k. Tight designs are those in which each pair is covered exactly once. We present constructions of tight dccd’s for arbitrary v when k = 2 and minimal constructions for v <= 20 when k = 4. A general, but not minimal, method is presented to construct circular dccd for arbitrary v when k = 4.

Linear characters of finite groups can be extended to take k operands. The basics of such a k-fold extension are detailed. We then examine a proposition by Johnson and Sehgal pertaining to these k-characters and disprove its converse. Probabilistic models can be applied to random walks on the Cayley groups of finite order. We examine random walks on dihedral groups which converge after a finite number of steps to the random walk induced by the uniform distribution. We present both sufficient and necessary conditions for such convergence and analyze aspects of algebraic geometry related to this subject.

We construct a covering system whose minimum modulus is 42. This improves the previous record of 40 by P. Nielsen.

No description available.

Let F and H be two (compatible) classes of functions. We observe that even when both F and H have small capacities as measured by their uniform covering numbers, the capacity of the composition class H o F={h o f| f in F, h in H} can become prohibitively large or even unbounded. To this end, in this thesis we provide a framework for controlling the capacity of composition and extend our results to bound the capacity of neural networks. Composition of Random Classes: We show that adding a small amount of Gaussian noise to the output of cF before composing it with H can effectively control the capacity of H o F, offering a general recipe for modular design. To prove our results, we define new notions of uniform covering number of random functions with respect to the total variation and Wasserstein distances. The bounds for composition then come naturally through the use of data processing inequality. Capacity of Neural Networks: We instantiate our results for the case of sigmoid neural networks. We start by finding a bound for the single-layer noisy neural network by estimating input distributions with mixtures of Gaussians and covering them. Next, we use our composition theorems to propose a novel bound for the covering number of a multi-layer network. This bound does not require Lipschitz assumption and works for networks with potentially large weights. Empirical Investigation of Generalization Bounds: We include preliminary empirical results on MNIST dataset to compare several covering number bounds based on their suggested generalization bounds. To compare these bounds, we propose a new metric (NVAC) that measures the minimum number of samples required to make the bound non-vacuous. The empirical results indicate that the amount of noise required to improve over existing uniform bounds can be numerically negligible. The source codes are available at https://github.com/fathollahpour/composition_noise / Thesis / Master of Science (MSc) / Given two classes of functions with bounded capacity, is there a systematic way to bound the capacity of their composition? We show that this is not generally true. Capacity of a class of functions is a learning-theoretic quantity that may be used to explain its sample complexity and generalization behaviour. In other words, bounding the capacity of a class can be used to ensure that given enough samples, with high probability, the deviation between training and expected errors is small. In this thesis, we show that adding a small amount of Gaussian noise to the output of functions can effectively control the capacity of composition, introducing a general framework for modular design. We instantiate our results for sigmoid neural networks and derive capacity bounds that work for networks with large weights. Our empirical results show that the amount of Gaussian noise required to improve over existing bounds is negligible.

The current debates on abolishing hijabs in the European Union have seen many countries absolish headscarves. Nations including France, Belgium, and Austria are among the countries that have banned hijabs in public spaces. However, in Sweden, various bills have been presented in the parliament. The aimed to investigate wheather Hijab and other Islamic covering should be banned in Sweden. The current study adopted a systematic literature review that included 16 studies on the debates about banning the Hijab. The study's findings confirm that the call for a ban on Hijab in Sweden are unjustified and influenced by the oversimplification of the Islamic cultures. Besides, the assertions of the study indicate that the European nations unlawfully targeted Muslims, subjecting them to islamophobia and hate crimes.

The objective of this research is to devise a procedure to generate random Set Covering Problem (SCP) instances with known optimal solutions and correlated coefficients. The procedure presented in this work can generate a virtually unlimited number of SCP instances with known optimal solutions and realistic characteristics, thereby facilitating testing of the performance of SCP heuristics and algorithms. A four-phase procedure based on the Karush-Kuhn-Tucker (KKT) conditions is proposed to generate SCP instances with known optimal solutions and correlated coefficients. Given randomly generated values for the objective function coefficients and the sum of the binary constraint coefficients for each variable and a randomly selected optimal solution, the procedure: (1) calculates the range for the number of possible constraints, (2) generates constraint coefficients for the variables with value one in the optimal solution, (3) assigns values to the dual variables, and (4) generates constraint coefficients for variables with value 0 in the optimal solution so that the KKT conditions are satisfied. A computational demonstration of the procedure is provided. A total of 525 SCP instances are simulated under seven correlation levels and three levels for the number of constraints. Each of these instances is solved using three simple heuristic procedures. The performance of the heuristics on the SCP instances generated is summarized and analyzed. The performance of the heuristics generally worsens as the expected correlation between the coefficients increases and as the number of constraints increases. The results provide strong evidence of the benefits of the procedure for generating SCP instances with correlated coefficients, and in particular SCP instances with known optimal solutions.

This thesis describes the implementation of a covering algorithm for semantic decomposition of sentences of technical patents. This research complements the ASPIN project that has a long term goal of providing an automated system for digital system synthesis from patents. In order to develop a prototype of the system explained in a patent, a natural language processor (sentence-interpreter) is required. These systems typically attempt to interpret a sentence by syntactic analysis (parsing) followed by semantic analysis. Quite often, the technical narrative contains grammatical errors, incomplete sentences, anaphoric references and typological errors that can cause the grammatical parse to fail. In such situations, an alternate method that uses a repository of pre-compiled, simple sentences (called frames) to analyze the sentences of the patent can be a useful back up. By semantically decomposing the sentences of patents to a set of frames whose meanings are fully understood, the meaning of the patent sentences can be interpreted. This thesis deals with the semantic decomposition of sentences using a branch and bound covering algorithm. The algorithm is implemented in C++. A number of experiments were conducted to evaluate the performance of this algorithm. The covering algorithm uses a standard branch and bound algorithm to semantically decompose sentences. The algorithm is fast, flexible and can provide good (100 % coverage for some sentences) coverage results. The system covered 67.68 % of the sentence tokens using 3459 frames in the repository. 54.25% of the frames identified by the system in covers for sentences, were found to be semantically correct. The experiments suggest that the performance of the system can be improved by increasing the number of frames in the repository. / Master of Science

Recently, covering arrays have been the subject of considerable research attention as they hold both theoretical interest and practical importance due to their applications to testing. In this thesis, we perform the first comprehensive study of a generalization of covering arrays called variable strength covering arrays, where we dictate the interactions to be covered in the array by modeling them as facets of an abstract simplicial complex. We outline the necessary background in the theory of hypergraphs, combinatorial testing, and design theory that is relevant to the study of variable strength covering arrays. We then approach questions that arise in variable strength covering arrays in a number of ways. We demonstrate their connections to hypergraph homomorphisms, and explore the properties of a particular family of abstract simplicial complexes, the qualitative independence hypergraphs. These hypergraphs are tightly linked to variable strength covering arrays, and we determine and identify several of their important properties and subhypergraphs. We give a detailed study of constructions for variable strength covering arrays, and provide several operations and divide-and-conquer techniques that can be used in building them. In addition, we give a construction using linear feedback shift registers from primitive polynomials of degree 3 over arbitrary finite fields to find variable strength covering arrays, which we extend to strength-3 covering arrays whose sizes are smaller than many of the best known sizes of covering arrays. We then give an algorithm for creating variable strength covering arrays over arbitrary abstract simplicial complexes, which builds the arrays one row at a time, using a density concept to guarantee that the size of the resultant array is asymptotic in the logarithm of the number of facets in the abstact simplicial complex. This algorithm is of immediate practical importance, as it can be used to create test suites for combinatorial testing. Finally, we use the Lovasz Local Lemma to nonconstructively determine upper bounds on the sizes of arrays for a number of different families of hypergraphs. We lay out a framework that can be used for many hypergraphs, and then discuss possible strategies that can be taken in asymmetric problems.

Recently, covering arrays have been the subject of considerable research attention as they hold both theoretical interest and practical importance due to their applications to testing. In this thesis, we perform the first comprehensive study of a generalization of covering arrays called variable strength covering arrays, where we dictate the interactions to be covered in the array by modeling them as facets of an abstract simplicial complex. We outline the necessary background in the theory of hypergraphs, combinatorial testing, and design theory that is relevant to the study of variable strength covering arrays. We then approach questions that arise in variable strength covering arrays in a number of ways. We demonstrate their connections to hypergraph homomorphisms, and explore the properties of a particular family of abstract simplicial complexes, the qualitative independence hypergraphs. These hypergraphs are tightly linked to variable strength covering arrays, and we determine and identify several of their important properties and subhypergraphs. We give a detailed study of constructions for variable strength covering arrays, and provide several operations and divide-and-conquer techniques that can be used in building them. In addition, we give a construction using linear feedback shift registers from primitive polynomials of degree 3 over arbitrary finite fields to find variable strength covering arrays, which we extend to strength-3 covering arrays whose sizes are smaller than many of the best known sizes of covering arrays. We then give an algorithm for creating variable strength covering arrays over arbitrary abstract simplicial complexes, which builds the arrays one row at a time, using a density concept to guarantee that the size of the resultant array is asymptotic in the logarithm of the number of facets in the abstact simplicial complex. This algorithm is of immediate practical importance, as it can be used to create test suites for combinatorial testing. Finally, we use the Lovasz Local Lemma to nonconstructively determine upper bounds on the sizes of arrays for a number of different families of hypergraphs. We lay out a framework that can be used for many hypergraphs, and then discuss possible strategies that can be taken in asymmetric problems.