Magliveras, Spyros S.

A finite cover C of a group G is a finite collection of proper subgroups of G such that G is equal to the union of all of the members of C. Such a cover is called minimal if it has the smallest cardinality among all finite covers of G. The covering number of G, denoted by σ(G), is the number of subgroups in a minimal cover of G. Here we determine the covering numbers of the projective special unitary groups U3(q) for q ≤ 5, and give upper and lower bounds for the covering number of U3(q) when q > 5. We also determine the covering number of the McLaughlin sporadic simple group, and verify previously known results on the covering numbers of the Higman-Sims and Held groups.

It was not until the 20th century that combinatorial design theory was studied as a formal subject. This field has many applications, for example in statistical experimental design, coding theory, authentication codes, and cryptography. Major approaches to the problem of discovering new t-designs rely on (i) the construction of large sets of t designs, (ii) using prescribed automorphism groups, (iii) recursive construction methods. In 2017 and 2018, Tran Van Trung introduced new recursive techniques to construct t – (v, k, λ) designs. These methods are of purely combinatorial nature and require using "ingredient" t-designs or resolutions whose parameters satisfy a system of non-linear equations. Even after restricting the range of parameters in this new method, the task is computationally intractable. In this work, we enhance Tran Van Trung's "Basic Construction" by a robust and efficient hybrid computational apparatus which enables us to construct hundreds of thousands of new t – (v, k, Λ) designs from previously known ingredient designs. Towards the end of the dissertation we also create a new family of 2-resolutions, which will be infinite if there are infinitely many Sophie Germain primes.

Any group with a finite noncyclic homomorphic image is a finite union of proper subgroups. Given such
a group G, we define the covering number of G to be the least positive integer m such that G is the
union of m proper subgroups. We present recent results on the determination of the covering numbers
of the alternating groups on nine and eleven letters.

Let V be an n-dimensional vector space over the field of q elements. By a geometric t-[qn,k,λ]
design we mean a collection D of k-dimensional subspaces if V, called blocks, such that every tdimensional
subspace T of V appears in exactly λ blocks in D. In a recent paper Braun, Kohnert,
Ӧstergård, and Wassermann constructed the first ever known large set LS[N][2,k,qn], namely an
LS[3][2,3,28] under a cyclic group G of order 255. In this work we construct an additional 8 large
sets with the same parameters, using the L3 algorithm for lattice basis-reduction.

The shortest vector problem SVP is de ned as follows: For a given basis B of an integral
lattice L fi nd a vector v in L whose length is minimal. Here we present the result of our
experiments based on a hill climbing algorithm using a computer cluster and a number of parallel
executions of a standard basis reduction technique, such as LLL, to successfully reduce an initial
basis of L. We begin by reducing ideal lattices of relatively small dimension and progressively
reduce ideal lattices of higher dimension, beating several earlier published solutions to the
approximate SVP problem.

With the publication of Shor's quantum algorithm for solving discrete logarithms in
finite cyclic groups, a need for new cryptographic primitives arose; namely, for more secure
primitives that would prevail in the post-quantum era.
The aim of this dissertation is to exploit some hard problems arising from group theory
for use in cryptography. Over the years, there have been many such proposals. We first look
at two recently proposed schemes based on some form of a generalization of the discrete
logari thm problem (DLP), identify their weaknesses, and cryptanalyze them.
By applying the exper tise gained from the above cryptanalyses, we define our own
generalization of the DLP to arbitrary finite groups. We show that such a definition leads
to the design of signature schemes and pseudo-random number generators with provable
security under a security assumption based on a group theoretic problem. In particular,
our security assumption is based on the hardness of factorizing elements of the projective
special linear group over a finite field in some representations. We construct a one-way
function based on this group theoretic assumption and provide a security proof.

The hidden subgroup problem has been an active topic of research in quantum
computing for over the past 10 years. Out of all the literature that is out there on this
topic, there are very few survey articles which discuss most or all of the details concerning
the Abelian hidden subgroup problem. As a matter of fact , many articles [17, 26 , 22, 45]
claim that an eff-icient quantum algorithm for the Abelian hidden subgroup problem
is folklore. To quote Jozsa [21]: " ... the detailed description of an efficient quantum
algorithm for the general abelian hidden subgroup problem seems not to have been
described in the literature." Apart from banishing this folklore, the aim of this work is
to serve as a monograph about the Abelian hidden subgroup, discussing many of the finer
points that are ignored in the literature so as to make it accessible and comprehensible
to the mathematically mature reader.

Let V be an n-dimensional vector space over the field of q elements. By a geometric t-[q^n, k, λ] design we mean a collection D of k-dimensional subspaces of V, called blocks, such that every t-dimensional subspace T of V appears in exactly λ blocks in D. A large set, LS [N] [t, k, q^n], of geometric designs is a collection on N disjoint t-[q^n, k, λ] designs that partitions [V K], the collection of k-dimensional subspaces of V. In this work we construct non-isomorphic large sets using methods based on incidence structures known as the Kramer-Mesner matrices. These structures are induced by particular group actions on the collection of subspaces of the vector space V. Subsequently, we discuss and use computational techniques for solving certain linear problems of the form AX = B, where A is a large integral matrix and X is a {0,1} solution. These techniques involve (i) lattice basis-reduction, including variants of the LLL algorithm, and (ii) linear programming. Inspiration came from the 2013 work of Braun, Kohnert, Ostergard, and Wassermann, [17], who produced the first nontrivial large set of geometric designs with t ≥ 2. Bal Khadka and Michael Epstein provided the know-how for using the LLL and linear programming algorithms that we implemented to construct the large sets.

The mathematical theory of nding a basis of shortest possible vectors in a
given lattice L is known as reduction theory and goes back to the work of Lagrange,
Gauss, Hermite, Korkin, Zolotarev, and Minkowski. Modern reduction theory is voluminous
and includes the work of A. Lenstra, H. Lenstra and L. Lovasz who created
the well known LLL algorithm, and many other researchers such as L. Babai and C. P.
Schnorr who created signi cant new variants of basis reduction algorithms. The shortest
vector (SVP) and closest vector (CVP) problems, presently considered intractable,
are algorithmic tasks that lie at the core of many number theoretic problems, integer
programming, nding irreducible factors of polynomials, minimal polynomials of algebraic
numbers, and simultaneous diophantine approximation. Lattice basis reduction
also has deep and extensive connections with modern cryptography, and cryptanalysis
particularly in the post-quantum era. In this dissertation we study and compare
current systems LLL and BKZ, and point out their strengths and drawbacks. In
addition, we propose and investigate the e cacy of new optimization techniques, to
be used along with LLL, such as hill climbing, random walks in groups, our lattice
di usion-sub lattice fusion, and multistage hybrid LDSF-HC technique. The rst two methods rely on the sensitivity of LLL to permutations of the
input basis B, and optimization ideas over the symmetric group Sm viewed as a
metric space. The third technique relies on partitioning the lattice into sublattices,
performing basis reduction in the partition sublattice blocks, fusing the sublattices,
and repeating. We also point out places where parallel computation can reduce runtimes
achieving almost linear speedup. The multistage hybrid technique relies on the
lattice di usion and sublattice fusion and hill climbing algorithms. Unlike traditional
methods, our approach brings in better results in terms of basis reduction towards
nding shortest vectors and minimal weight bases. Using these techniques we have
published the competitive lattice vectors of ideal lattice challenge on the lattice hall of
fame. Toward the end of the dissertation we also discuss applications to the multidimensional
knapsack problem that resulted in the discovery of new large sets of
geometric designs still considered very rare. The research introduces innovative techniques
in lattice basis reduction theory and provides some space for future researchers
to contemplate lattices from a new viewpoint.

Every transitive permutation representation of a finite group is the representation of the group in its action on the cosets of a particular subgroup of the group. The group has a certain rank for each of these representations. We first find almost all rank-3 and rank-4 transitive representations of the projective special linear group P SL(2, q) where q = pm and p is an odd prime. We also determine the rank of P SL (2, p) in terms of p on the cosets of particular given subgroups. We then investigate the construction of rank-3 transitive and primitive extensions of a simple group, such that the extension group formed is also simple. In the latter context we present a new, group theoretic construction of the famous Hoffman-Singleton graph as a rank-3 graph.