(S. Magliveras, A. Meyerowitz, and W. Kalies)
Funded by the NSF
In this project, we plan to investigate algorithmic solutions to several open problems in
combinatorics and graph theory. Researchers in the Department of Mathematical Sciences and the Center for Cryptology and Information Security
intend to implement three projects on the proposed cluster. The projects are as follows:
- Random walks in the unimodular group for lattice basis reduction
- Solving large multidimentional symmetric binary knapsacks with applications to the construction of t-designs
- Construction (or non-existence) of the Moore graph of degree 57
Problems such as finding a minimum basis in an integral lattice L are known to be computationally intractable. On the other hand, many hard problems in seemingly diverse areas can be transformed into problems of determining a sufficiently short, nontrivial vector in an appropriate lattice L. Examples abound in cryptology, optimization, or the construction of combinatorial designs. A polynomial time algorithm, known as the L3 algorithm, and its more efficient variants, has been known for over 20 years. Under certain conditions such algorithms can determine a sufficiently short basis for L. In practice, L3 works well only for lattices of relatively small dimension, with additional conditions on the density of L. Since any two bases B1 and B2 of L are related by B2 = MB1, where M is some unimodular integral matrix, one may wish to take a random walk in the unimodular group and attempt a hill descent or similar optimization process using an objective function appropriate to the problem, while first converting the unimodular group into a metric space by imposing an appropriate distance function. We investigate codes in the unimodular group, one of them being the symmetric group of permutation matrices, taking a particular starting point, taking a sample in a neighborhood of fixed radius, and selecting a best basis in the neighborhood, followed by repetition of the process. An L3 operation is executed at each neighborhood point and all these can be done in parallel and independently at each step. In a cluster of N parallel processors, we can afford to have a neighborhood sample of size N at each point of the random walk. This reduces computation time almost by a factor of N. In many problems presented, the lattice has a non-trivial automorphism group, and our algorithm utilizes this to affect an additional significant decrease in time complexity.
Binary Knapsack
Problems in the area of finite geometry & combinatorial designs involve solving a matrix equation of the form XA = B, where A and B are given, A is an n × m integer matrix, with n much larger than m, and typically, X is a 0-1 vector. In many problems A is also a 0-1 matrix and B a vector of which all entries are equal to some value λ. We have developed a branch-and-bound algorithm called SYNTH which can solve very large knapsacks of the above type in a very economical way. Although in the worst case SYNTH is of exponential time complexity, it is highly parallelizable, and takes into account the automorphism group of the underlying combinatorial structure. We wish to redesign SYNTH for the cluster of parallel machines, and use it in a systematic search for Steiner systems of type t − (v, k, λ) with 6 ≤ t < k < v, and λ = 1. Finding even one Steiner system with t = 6 would be an extremely significant result in the area of combinatorial designs; such systems have been sought unsuccessfully for over 100 years.
Moore Graph
A Moore Graph is a graph with diameter d and girth 2d + 1. The complete graphs and odd cycles are trivial examples. Exactly two non-trivial examples are known and are easy to construct: the Petersen graph and the Hoffman-Singleton graph. It can be shown that, surprisingly, just one more nontrivial Moore graph is possible, one of degree 57, on 3250 vertices. In spite of considerable efforts in the past to construct the graph or prove it does not exist, such endeavors have been unsuccessful. It has been shown that if the graph exists, it will have a trivial automorphism group, a fact that makes its construction much harder. Although even regularity is not obvious, a Moore graph must be distance-regular. The examples above are distance transitive, and have many important associated designs. We propose to investigate the one remaining case: A regular graph with valency 57, diameter two and girth five. We will first look for certain potential quotient structures whose existence would be quite interesting in itself. If they do not exist, this will argue strongly against the existence of such a graph. If they do exist, we will have a good chance to construct this elusive graph.
The solutions for both the random walk and the Moore graph problems require first a space
partition of a data set, followed by assigning each part to different processors for processing, with results collected at a designated
node (any processor in the SGI supercluster). Shared-memory space eliminates the need of distributing partitioned data sets. The binary
knapsack involves branch-and-bound. Static partitioning is not sufficient, since the workload of each part is not known a priori. Therefore,
task scheduling and redistribution are needed. We plan to use the TICC technology developed at EDSS, Inc. for load balancing on the SGI
supercluster.