Current Search: Combinatorial analysis. (x)
View All Items
 Title
 Techniques in Lattice Basis Reduction.
 Creator
 Khadka, Bal K., Magliveras, Spyros S., Florida Atlantic University, Charles E. Schmidt College of Science, Department of Mathematical Sciences
 Abstract/Description

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...
Show moreThe 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 postquantum 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 usionsub lattice fusion, and multistage hybrid LDSFHC 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.
Show less  Date Issued
 2016
 PURL
 http://purl.flvc.org/fau/fd/FA00004678
 Subject Headings
 Cryptography., Combinatorial analysis., Group theory.
 Format
 Document (PDF)
 Title
 LONESUM MATRICES AND ACYCLIC ORIENTATIONS: ENUMERATION AND ASYMPTOTICS.
 Creator
 Khera, Jessica, Lundberg, Erik, Florida Atlantic University, Department of Mathematical Sciences, Charles E. Schmidt College of Science
 Abstract/Description

An acyclic orientation of a graph is an assignment of a direction to each edge in a way that does not form any directed cycles. Acyclic orientations of a complete bipartite graph are in bijection with a class of matrices called lonesum matrices, which can be uniquely reconstructed from their row and column sums. We utilize this connection and other properties of lonesum matrices to determine an analytic form of the generating function for the length of the longest path in an acyclic...
Show moreAn acyclic orientation of a graph is an assignment of a direction to each edge in a way that does not form any directed cycles. Acyclic orientations of a complete bipartite graph are in bijection with a class of matrices called lonesum matrices, which can be uniquely reconstructed from their row and column sums. We utilize this connection and other properties of lonesum matrices to determine an analytic form of the generating function for the length of the longest path in an acyclic orientation on a complete bipartite graph, and then study the distribution of the length of the longest path when the acyclic orientation is random. We use methods of analytic combinatorics, including analytic combinatorics in several variables (ACSV), to determine asymptotics for lonesum matrices and other related classes.
Show less  Date Issued
 2021
 PURL
 http://purl.flvc.org/fau/fd/FA00013716
 Subject Headings
 Matrices, Combinatorial analysis, Graph theory
 Format
 Document (PDF)
 Title
 SOLVING V.I. ARNOLD’S PROBLEM ABOUT ASYMPTOTIC ENUMERATION OF MORSE FUNCTIONS ON THE 2SPHERE: A COMBINATORIAL AND ANALYTIC APPROACH WITH COMPUTER ASSISTED PROOFS.
 Creator
 Dhakal, Bishal, MirelesJames, Jason, Florida Atlantic University, Department of Mathematical Sciences, Charles E. Schmidt College of Science
 Abstract/Description

The goal of this dissertation is to estimate the precise asymptotics for the number of geometric equivalence classes of Morse functions on the 2sphere. Our approach involves utilizing the Lagrange inversion formula, Cauchy’s coefficient formula, and the saddle point method for the asymptotic analysis of contour integrals to analyze the generating function derived by L. Nicolaescu, expressed as the inverse of an elliptic integral. We utilize complex analysis, nonlinear functional analysis in...
Show moreThe goal of this dissertation is to estimate the precise asymptotics for the number of geometric equivalence classes of Morse functions on the 2sphere. Our approach involves utilizing the Lagrange inversion formula, Cauchy’s coefficient formula, and the saddle point method for the asymptotic analysis of contour integrals to analyze the generating function derived by L. Nicolaescu, expressed as the inverse of an elliptic integral. We utilize complex analysis, nonlinear functional analysis in infinite sequence spaces, and interval arithmetic to write all the necessary MATLAB programs that validate our results. This work answers questions posed by Arnold and Nicolaescu, furthering our understanding of the topological properties of Morse functions on twodimensional manifolds. It also demonstrates the effectiveness of a computer assisted approach for asymptotic analysis.
Show less  Date Issued
 2023
 PURL
 http://purl.flvc.org/fau/fd/FA00014264
 Subject Headings
 Manifolds (Mathematics), Morse theory, Combinatorial analysis
 Format
 Document (PDF)
 Title
 Avoiding abelian squares in infinite partial words.
 Creator
 Severa, William., Harriet L. Wilkes Honors College
 Abstract/Description

Famous mathematician Paul Erdèos conjectured the existence of infinite sequences of symbols where no two adjacent subsequences are permutations of one another. It can easily be checked that no such sequence can be constructed using only three symbols, but as few as four symbols are sufficient. Here, we expand this concept to include sequences that may contain 'do not know'' characters, called holes. These holes make the undesired subsequences more common. We explore both finite and infinite...
Show moreFamous mathematician Paul Erdèos conjectured the existence of infinite sequences of symbols where no two adjacent subsequences are permutations of one another. It can easily be checked that no such sequence can be constructed using only three symbols, but as few as four symbols are sufficient. Here, we expand this concept to include sequences that may contain 'do not know'' characters, called holes. These holes make the undesired subsequences more common. We explore both finite and infinite sequences. For infinite sequences, we use iterating morphisms to construct the nonrepetitive sequences with either a finite number of holes or infinitely many holes. We also discuss the problem of using the minimum number of different symbols.
Show less  Date Issued
 2010
 PURL
 http://purl.flvc.org/FAU/3335460
 Subject Headings
 Abelian groups, Mathematics, Study and teaching (Higher), Combinatorial analysis, Combinatorial set theory, Probabilities
 Format
 Document (PDF)
 Title
 The enumeration of lattice paths and walks.
 Creator
 Gao, Shanzhen., Charles E. Schmidt College of Science, Department of Mathematical Sciences
 Abstract/Description

A wellknown long standing problem in combinatorics and statistical mechanics is to find the generating function for selfavoiding walks (SAW) on a twodimensional lattice, enumerated by perimeter. A SAW is a sequence of moves on a square lattice which does not visit the same point more than once. It has been considered by more than one hundred researchers in the pass one hundred years, including George Polya, Tony Guttmann, Laszlo Lovasz, Donald Knuth, Richard Stanley, Doron Zeilberger,...
Show moreA wellknown long standing problem in combinatorics and statistical mechanics is to find the generating function for selfavoiding walks (SAW) on a twodimensional lattice, enumerated by perimeter. A SAW is a sequence of moves on a square lattice which does not visit the same point more than once. It has been considered by more than one hundred researchers in the pass one hundred years, including George Polya, Tony Guttmann, Laszlo Lovasz, Donald Knuth, Richard Stanley, Doron Zeilberger, Mireille BousquetMlou, Thomas Prellberg, Neal Madras, Gordon Slade, Agnes Dit tel, E.J. Janse van Rensburg, Harry Kesten, Stuart G. Whittington, Lincoln Chayes, Iwan Jensen, Arthur T. Benjamin, and many others. More than three hundred papers and a few volumes of books were published in this area. A SAW is interesting for simulations because its properties cannot be calculated analytically. Calculating the number of selfavoiding walks is a common computational problem. A recently proposed model called prudent selfavoiding walks (PSAW) was first introduced to the mathematics community in an unpublished manuscript of Pra, who called them exterior walks. A prudent walk is a connected path on square lattice such that, at each step, the extension of that step along its current trajectory will never intersect any previously occupied vertex. A lattice path composed of connected horizontal and vertical line segments, each passing between adjacent lattice points. We will discuss some enumerative problems in selfavoiding walks, lattice paths and walks with several step vectors. Many open problems are posted.
Show less  Date Issued
 2011
 PURL
 http://purl.flvc.org/FAU/3183129
 Subject Headings
 Combinatorial analysis, Approximation theory, Mathematical statistics, Limit theorems (Probabilty theory)
 Format
 Document (PDF)
 Title
 New Geometric Large Sets.
 Creator
 Hurley, Michael Robert, Magliveras, Spyros S., Florida Atlantic University, Charles E. Schmidt College of Science, Department of Mathematical Sciences
 Abstract/Description

Let V be an ndimensional vector space over the field of q elements. By a geometric t[q^n, k, λ] design we mean a collection D of kdimensional subspaces of V, called blocks, such that every tdimensional 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 kdimensional subspaces of V. In this work we construct nonisomorphic large sets using...
Show moreLet V be an ndimensional vector space over the field of q elements. By a geometric t[q^n, k, λ] design we mean a collection D of kdimensional subspaces of V, called blocks, such that every tdimensional 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 kdimensional subspaces of V. In this work we construct nonisomorphic large sets using methods based on incidence structures known as the KramerMesner 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 basisreduction, 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 knowhow for using the LLL and linear programming algorithms that we implemented to construct the large sets.
Show less  Date Issued
 2016
 PURL
 http://purl.flvc.org/fau/fd/FA00004732, http://purl.flvc.org/fau/fd/FA00004732
 Subject Headings
 Group theory., Finite groups., Factorial experiment designs., Irregularities of distribution (Number theory), Combinatorial analysis.
 Format
 Document (PDF)
 Title
 Distinguishability of Public Keys and Experimental Validation: The McEliece PublicKeyed Cryptosystem.
 Creator
 Pham, Hai, Steinwandt, Rainer, Florida Atlantic University, Charles E. Schmidt College of Science, Department of Mathematical Sciences
 Abstract/Description

As quantum computers continue to develop, they pose a threat to cryptography since many popular cryptosystems will be rendered vulnerable. This is because the security of most currently used asymmetric systems requires the computational hardness of the integer factorization problem, the discrete logarithm or the elliptic curve discrete logarithm problem. However, there are still some cryptosystems that resist quantum computing. We will look at codebased cryptography in general and the...
Show moreAs quantum computers continue to develop, they pose a threat to cryptography since many popular cryptosystems will be rendered vulnerable. This is because the security of most currently used asymmetric systems requires the computational hardness of the integer factorization problem, the discrete logarithm or the elliptic curve discrete logarithm problem. However, there are still some cryptosystems that resist quantum computing. We will look at codebased cryptography in general and the McEliece cryptosystem specifically. Our goal is to understand the structure behind the McEliece scheme, including the encryption and decryption processes, and what some advantages and disadvantages are that the system has to offer. In addition, using the results from Courtois, Finiasz, and Sendrier's paper in 2001, we will discuss a digital signature scheme based on the McEliece cryptosystem. We analyze one classical algebraic attack against the security analysis of the system based on the distinguishing problem whether the public key of the McEliece scheme is generated from a generating matrix of a binary Goppa code or a random binary matrix. The idea of the attack involves solving an algebraic system of equations and we examine the dimension of the solution space of the linearized system of equations. With the assistance from a paper in 2010 by Faugere, GauthierUmana, Otmani, Perret, Tillich, we will see the parameters needed for the intractability of the distinguishing problem.
Show less  Date Issued
 2015
 PURL
 http://purl.flvc.org/fau/fd/FA00004535, http://purl.flvc.org/fau/fd/FA00004535
 Subject Headings
 Coding theory, Combinatorial analysis, Data encryption (Computer science), Data transmission systems  Security measures, Information theory, McEliece, Robert J.  Influence, Public key cryptography
 Format
 Document (PDF)