Current Search:  Combinatorial analysis. (x)

View All Items

  • CSV Spreadsheet
(1 - 7 of 7)
Techniques in Lattice Basis Reduction
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 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.
Show less
Date Issued
2016
PURL
http://purl.flvc.org/fau/fd/FA00004678
Subject Headings
Cryptography., Combinatorial analysis., Group theory.
Format
Document (PDF)
LONESUM MATRICES AND ACYCLIC ORIENTATIONS: ENUMERATION AND ASYMPTOTICS
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)
SOLVING V.I. ARNOLD’S PROBLEM ABOUT ASYMPTOTIC ENUMERATION OF MORSE FUNCTIONS ON THE 2-SPHERE: A COMBINATORIAL AND ANALYTIC APPROACH WITH COMPUTER ASSISTED PROOFS
Title
SOLVING V.I. ARNOLD’S PROBLEM ABOUT ASYMPTOTIC ENUMERATION OF MORSE FUNCTIONS ON THE 2-SPHERE: A COMBINATORIAL AND ANALYTIC APPROACH WITH COMPUTER ASSISTED PROOFS.
Creator
Dhakal, Bishal, Mireles-James, 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 2-sphere. 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 2-sphere. 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 two-dimensional 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)
Avoiding abelian squares in infinite partial words
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 non-repetitive 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)
enumeration of lattice paths and walks
Title
The enumeration of lattice paths and walks.
Creator
Gao, Shanzhen., Charles E. Schmidt College of Science, Department of Mathematical Sciences
Abstract/Description
A well-known long standing problem in combinatorics and statistical mechanics is to find the generating function for self-avoiding walks (SAW) on a two-dimensional 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 well-known long standing problem in combinatorics and statistical mechanics is to find the generating function for self-avoiding walks (SAW) on a two-dimensional 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 Bousquet-Mlou, 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 self-avoiding walks is a common computational problem. A recently proposed model called prudent self-avoiding 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 self-avoiding 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)
New Geometric Large Sets
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 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...
Show moreLet 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.
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)
Distinguishability of Public Keys and Experimental Validation: The McEliece Public-Keyed Cryptosystem
Title
Distinguishability of Public Keys and Experimental Validation: The McEliece Public-Keyed 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 code-based 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 code-based 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, Gauthier-Umana, 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)