In many investigations, an experimenter is interested in comparing the effects of a number of experimental treatments, such as yields of several new agriculture varieties, results of several different production procedures, or effects of various raw materials on a final product. In this type of investigation, an F test of the mean square for treatments is often used to test the hypothesis that all treatment means are homogeneous. Given that this hypothesis can be rejected, the experimenter would like to make decisions about the significances of individual differences among treatment means considered a pair at a time. / Master of Science

The problem considered in this paper is that of estimating several missing values and analyzing the resulting augmented data in a balanced incomplete block design. The estimates are obtained by Yates' procedure of minimizing the error sum of squares. Explicit formulae are obtained for all cases involving not more than two missing values and for several particular configurations of the missing values within the design. A general solution is obtained which involves the inversion of a symmetric n-square matrix, where n is the number of missing values. An exact analysis of data augmented by missing value estimates is given which eliminates a positive bias in the treatment sum of squares. It is possible to treat a balanced incomplete block design as a randomized block design with missing values. Estimates of the missing entries and a randomized block analysis can then be obtained according to the methods of Glenn and Kramer. An example of this procedure is given, and the results are compared with the results obtained by the usual balanced incomplete block analysis. An example is given illustrating the techniques of missing value estimation and subsequent exact analysis for the balanced incomplete block design. / Master of Science

Les codes localement corrigibles ont été introduits dans le but d'extraire une partie de l'information contenue dans un mot de code bruité, en effectuant un nombre limité de requêtes à ses symboles, ce nombre étant appelé la localité du code. Ces dernières années ont vu la construction de trois familles de tels codes, dont la localité est sous-linéaire en la taille du message, et le rendement est arbitrairement grand. Ce régime de paramètres est particulièrement intéressant pour des considérations pratiques.Dans cette thèse, nous donnons une rapide revue de littérature des codes localement corrigibles, avant d'en proposer un modèle combinatoire générique, à base de block designs. Nous définissons et étudions ensuite un analogue, dans le cas projectif, des relèvements affine de codes introduits par Guo, Kopparty et Sudan. Nous établissons par ailleurs plusieurs liens entre ces deux familles, pour finir par une analyse précise de la structure monomiale de ces codes dans le cas du relèvement plan.Une deuxième partie de la thèse se focalise sur l'application de ces codes à deux protocoles cryptographiques. D'abord, nous proposons un protocole de récupération confidentielle d'information (private information retrieval, PIR) à partir de codes basés sur des designs transversaux, dont la taille des blocs s'apparente à la localité d'un code localement corrigible. Les protocoles ainsi construits ont l'avantage de n'exiger aucun calcul pour les serveurs, et de présenter une faible redondance de stockage ainsi qu'une complexité de communication modérée. Ensuite, nous donnons une construction générique de preuve de récupérabilité (proof of retrievability, PoR) à base de codes admettant une riche structure d'équations de parité à petit poids. Nous en donnons finalement une analyse de sécurité fine ainsi que plusieurs instanciations fondées sur des codes à propriétés locales. / Locally correctable codes (LCCs) were introduced in order to retrieve pieces of information from a noisy codeword, by using a limited number of queries to its symbols, this number being called the locality. Three main families of LCCs reaching sublinear locality and arbitrarily high rate have been built so far. This specific range of parameters is of particular interest concerning practical applications of LCCs.In this thesis, after giving a state of the art for LCCs, we study how they can be built using block designs. We then give an analogue over projective spaces of the family of affine lifted codes introduced by Guo, Kopparty and Sudan. We exhibit several links between both families, and we give a precise analysis of the monomial structure of the code in the case of the lifting of order 2.The second part of the thesis focuses on the application of these codes to two cryptographic protocols. We first build a new private informatin retrieval (PIR) protocol from codes based on transversal designs, whose block size defines the locality of the code. Our construction features no computation on the server side, low storage overhead and moderate communication complexity. Then, we propose a new generic construction of proof-of-retrievability (PoR) that uses codes equipped with an elaborate structure of low-weight parity-check equations. We give a rigorous analysis of the security of our scheme, and we finally propose practical instantiations based on codes with locality.

Thesis (M.Sc.)--Memorial University of Newfoundland, 2005. / Bibliography: leaves 78-83.

This project deals with the automorphism group G of a Steiner system S (3, 4, 10). S₁₀, the symmetrical group of degree 10, acts transitively on T, the set of all Steiner systems with parameters 3, 4, 10. The purpose of this project is to study the action of S₁₀ on cosets of G. This will be achieved by means of a graph of S₁₀ on T x T. The orbits of S₁₀ on T x T are in one-one correspondence with the orbits of G, the stabilizer of an S [e] T on T.

本研究旨在建立廣義線性模式下之D-與A-最適設計(optimal designs)，並依不同處理結構(treatment structure)分成完全隨機設計(completely randomized design, CRD)與隨機集區設計(randomized block design, RBD)兩部分探討。 根據完全隨機設計所推導出之行列式的性質與理論結果，我們首先提出一個能快速大幅限縮尋找D-最適正合(exact)設計範圍的演算法。解析解的部分，則從將v個處理的變異數分為兩類出發，建立其D-最適近似(approximate)設計，並由此發現 (1) 各水準對應之樣本最適配置的上下界並非與水準間不同變異有關，而是與有多少處理之變異相同有關；(2) 即使是變異很大的處理，也必須分配觀察值，始能極大化行列式值。此意味著當v較大時，均分應不失為一有效率(efficient)的設計。至於正合設計，我們僅能得出某一處理特別大或特別小時的D-最適設計，並舉例說明求不出一般解的原因。 除此之外，我們亦求出當三個處理的變異數皆不同時之D-最適近似設計，以及v個處理皆不同時之A-最適近似設計。 至於最適隨機集區設計的建立，我們的重點放在v=2及v=3的情形，並假設集區樣本數(block size)為給定。當v=2時，各集區對應之行列式值不受其他集區的影響，故僅需依照完全隨機設計之所得，將各集區之行列式值分別最佳化，即可得出D-與A-最適設計。值得一提的是，若進一步假設各集區中兩處理變異的比例(>1)皆相同，且集區大小皆相同，則將各處理的「近似設計下最適總和」取最接近的整數，再均分給各集區，其結果未必為最適設計。當v=3時，即使只有2個集區，行列式也十分複雜，我們目前僅能證明當集區內各處理的變異相同時(不同集區之處理變異可不同)，均分給定之集區樣本數為D-最適設計。當集區內各處理的變異不全相同時，我們僅能先以2個集區為例，類比完全隨機設計的性質，舉例猜想當兩集區中處理之變異大小順序相同時，各處理最適樣本配置的多寡亦與變異大小呈反比。由於本研究對處理與集區兩者之效應假設為可加，因此可合理假設集區中處理之變異大小順序相同。 / The problem of finding D- and A-optimal designs for the zero- and one-way elimination of heterogeneity under generalized linear models is considered. Since GLM designs rely on the values of parameters to be estimated, our strategy is to employ the locally optimal designs. For the zero-way elimination model, a theorem-based algorithm is proposed to search for the D-optimal exact designs. A formula for the construction of D-optimal approximate design when values of unknown parameters are split into two, with respective sizes m and v-m, are derived. Analytic solutions provided to the exact counterpart, however, are restricted to the cases when m=1 and m=v-1. An example is given to explain the problem involved. On the other hand, the upper bound and lower bound of the optimal number of replicates per treatment are proved dependent on m, rather than the unknown parameters. These bounds imply that designs having as equal number of replications for each treatment as possible are efficient in D-optimality. In addition, a D-optimal approximate design when values of unknown parameters are divided into three groups is also obtained. A closed-form expression for an A-optimal approximate design for comparing arbitrary v treatments is given. For the one-way elimination model, our focus is on studying the D-optimal designs for v=2 and v=3 with each block size given. The D- and A-optimality for v=2 can be achieved by assigning units proportional to square root of the ratio of two variances, which is larger than 1, to the treatment with smaller variance in each block separately. For v=3, the structure of determinant is much more complicated even for two blocks, and we can only show that, when treatment variances are the same within a block, design having equal number of replicates as possible in each block is a D-optimal block design. Some numerical evidences conjecture that a design satisfying the condition that the number of replicates are inversely proportional to the treatment variances per block is better in terms of D-optimality, as long as the ordering of treatment variances are the same across blocks, which is reasonable for an additive model as we assume.

實驗設計中，我們假設在區塊中存在一趨勢效應(trend effect)。此趨勢效應影響觀察值，也影響我們對區塊效應(block effect)和處理效應(treatment effect)的估計。此種設計模式不同於一般的區塊設計模式，因此須將趨勢效應加人設計模式中。 　　Bradley and Yeh (1980)研究和討論此種趨勢效應在區塊設計模式中之影響，並定義出無趨勢設計(trend-free design)。所謂無趨勢設計，乃是在區塊設計模式中，趨勢效應被抵消不影響處理效應之分析。Bradley and Yeh (1983)推導了一個線性無趨勢設計存在的必要條件是r(k+1)≡0(mod 2)其中k為區塊大小，r為處理出現的次數。 　　Bradley and Yeh進一步預測任一滿足r(k+1)≡0(mod2)的區塊設計，經過在區塊中處理位置調整後，可變為一個線性無趨勢設計。本篇論文的主要目的乃是在探討給定一GD設計(group-divisibledesigns)，檢驗和推導此預測是否為真。 / Yeh and Bradley conjectured that every binary connected block design with blocks of size k and a constant replication numberr for each treatment can be converted to a linear trend-free design by permuting the positions of theatments within blocks if and only if r(k+1)≡0 (mod 2). Chai and Majumdar (1993) proved that any BIB design which satisfies r(k+1)≡0 (mod 2) is even can be converted to a linear trend-free design. In this thesis, we want to examine this conjecture is true or not for group-divisible designs (GD designs).

在工業、農業、或醫藥界的實驗中，經常必須拿數個不同的試驗處理 (test treatments)和一個已使用過的對照處理(control treatment)比較 。所謂的試驗處理可能是數組新的儀器、不同配方的新藥、或不同成份的 肥料等。以實驗新藥為例，研藥者想決定是否能以新藥取代原來所使用的 藥，故對v種新藥與原藥做比較，評估其藥效之差異。為了降低實驗中不 必要的誤差以增加其準確性，集區設計成為實驗者常用的設計方法之一； 又因A式最適設計是我們欲估計的對照處理效果(effect)與試驗處理效果 之差異之估計值最小的設計，基於此良好的統計特性，我們選擇A式最適 性為評判根據。古典的A式最適性並未將對照處理與試驗處理所具備的先 前資訊(prior information)加以考慮，以上例而言，我們不可能對原來 使用的藥一無所知，經由過去的實驗或臨床的反應，研藥者必已對其藥性 有某種程度的了解，直觀上，這種過去經驗的累積，影響到實驗配置上， 可能使對照處理的實驗次數減少，相對地可對試驗處理多做實驗，設計遂 更具意義。因而本文考慮在k>v的情形下之貝式最適集區設計，對先前分 配施以某種限制，依據準確設計理論(exact design theory)，推導單項 異種消除模型(one- way elimination of heterogeneity model)之下的 貝氏A式最適設計與Γ- minimax最適設計，使Majumdar(1992)的結果能適 用於完全集區設計。此種設計對先前分配具有強韌性，即當先前分配有所 偏誤，且其誤差在某一範圍內時，此設計仍為最適設計或仍可維持所謂的 高效度(high efficiency)。本文將列舉許多實例以說明此一特性。 We consider the problem of comparing a set of v test treatments simultaneously with a control treatment when k>v. Following the work of Majumdar(1992), we use exact design theory to derive Bayes A-optimal designs and optimal Γ-minimax designs for the one-way elimination of heterogeneity model. These designs have the same properties as of Bayes A-optimal incomplete block designs. We also provide several examples of robust optimal designs and highly efficient designs.