Author name cluster

Brett Stevens

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

7 papers

1 author row

AAAI Conference 2022 Short Paper

Integer and Constraint Programming Revisited for Mutually Orthogonal Latin Squares (Student Abstract)

Noah Rubin
Curtis Bright
Brett Stevens
Kevin Cheung

We use integer programming (IP) and constraint programming (CP) to search for sets of mutually orthogonal latin squares (MOLS). We improve the performance of the solvers by formulating an extended symmetry breaking method and provide an alternative CP encoding which performs much better in practice. Using state-of-the-art solvers we are able to quickly find pairs of MOLS (or prove their nonexistence) in all orders up to and including eleven. We also analyze the effectiveness of using CP and IP solvers to search for triples of MOLS and estimate the running time of using this approach to resolve the longstanding open problem of determining the existence of a triple of MOLS of order ten.

PDF Details

AAAI Conference 2021 Conference Paper

A SAT-based Resolution of Lam’s Problem

Curtis Bright
Kevin K. H. Cheung
Brett Stevens
Ilias Kotsireas
Vijay Ganesh

In 1989, computer searches by Lam, Thiel, and Swiercz experimentally resolved Lam’s problem from projective geometry—the long-standing problem of determining if a projective plane of order ten exists. Both the original search and an independent verification in 2011 discovered no such projective plane. However, these searches were each performed using highly specialized custom-written code and did not produce nonexistence certificates. In this paper, we resolve Lam’s problem by translating the problem into Boolean logic and use satisfiability (SAT) solvers to produce nonexistence certificates that can be verified by a third party. Our work uncovered consistency issues in both previous searches—highlighting the difficulty of relying on specialpurpose search code for nonexistence results.

PDF Details

IJCAI Conference 2020 Conference Paper

Unsatisfiability Proofs for Weight 16 Codewords in Lam's Problem

Curtis Bright
Kevin K. H. Cheung
Brett Stevens
Ilias Kotsireas
Vijay Ganesh

In the 1970s and 1980s, searches performed by L. Carter, C. Lam, L. Thiel, and S. Swiercz showed that projective planes of order ten with weight 16 codewords do not exist. These searches required highly specialized and optimized computer programs and required about 2, 000 hours of computing time on mainframe and supermini computers. In 2010, these searches were verified by D. Roy using an optimized C program and 16, 000 hours on a cluster of desktop machines. We performed a verification of these searches by reducing the problem to the Boolean satisfiability problem (SAT). Our verification uses the cube-and-conquer SAT solving paradigm, symmetry breaking techniques using the computer algebra system Maple, and a result of Carter that there are ten nonisomorphic cases to check. Our searches completed in about 30 hours on a desktop machine and produced nonexistence proofs of about 1 terabyte in the DRAT (deletion resolution asymmetric tautology) format.

PDF Details DOI

TCS Journal 2019 Journal Article

Upper bounds on the sizes of variable strength covering arrays using the Lovász local lemma

Lucia Moura
Sebastian Raaphorst
Brett Stevens

Covering arrays are generalizations of orthogonal arrays that have been widely studied and are used in software testing. The probabilistic method has been employed to derive upper bounds on the sizes of minimum covering arrays and give asymptotic upper bounds that are logarithmic on the number of columns of the array. This corresponds to test suites with a desired level of coverage of the parameter space where we guarantee the number of test cases is logarithmic on the number of parameters of the system. In this paper, we study variable strength covering arrays, a generalization of covering arrays that uses a hypergraph to specify the sets of columns where coverage is required; (standard) covering arrays are the special case where coverage is required for all sets of columns of a fixed size t, its strength. We use the probabilistic method to obtain upper bounds on the number of rows of a variable strength covering array, given in terms of parameters of the hypergraph. We then compare this upper bound with another one given by a density-based greedy algorithm on different types of hypergraph such as t-designs, cyclic consecutive hypergraphs, planar triangulation hypergraphs, and a more specific hypergraph given by a clique of higher strength on top of a “base strength”. The conclusions are dependent on the class of hypergraph, and we discuss specific characteristics of the hypergraphs which are more amenable to using different versions of the Lovász local lemma.

Details DOI

TCS Journal 2009 Journal Article

Covering arrays avoiding forbidden edges

Peter Danziger
Eric Mendelsohn
Lucia Moura
Brett Stevens

Covering arrays (CAs) can be used to detect the existence of faulty pairwise interactions between parameters or components in a software system. The generalization considered here applies to the situation in which some input combinations are invalid, a requirement quite common in software testing. In this paper, we study covering arrays avoiding forbidden edges ( C A F E s), where certain pairwise interactions are forbidden while all others must be covered, and we aim to minimize the number of tests. We establish a theoretical framework for this problem, by providing connections to the edge clique covering problem, lower and upper bounds, complexity results and a recursive construction. We also give an algorithm for the case of binary alphabets.

Details DOI

TCS Journal 2004 Journal Article

Packing arrays

Brett Stevens
Eric Mendelsohn

A packing array is a b×k array of values from a g-ary alphabet such that given any two columns, i and j, and for all ordered pairs of elements from the g-ary alphabet, (g 1, g 2), there is at most one row, r, such that a r, i =g 1 and a r, j =g 2. A central question is to determine, for given g and k, the maximum possible b. We develop general direct and recursive constructions and upper bounds on the sizes of packing arrays. We introduce the consideration of a set of disjoint rows in a packing array which allows these constructions and additionally gives a new upper bound on the size of all packing arrays. We also show the equivalence of the problem to a matching problem on graphs and a class of resolvable pairwise balanced designs. We provide tables of the best known upper and lower bounds.

Details DOI

TCS Journal 2003 Journal Article

The anti-Oberwolfach solution: pancyclic 2-factorizations of complete graphs

Brett Stevens

We pose and completely solve the existence of pancyclic 2-factorizations of complete graphs and complete bipartite graphs. Such 2-factorizations exist for all such graphs, except a few small cases which we have proved are impossible. The solution method is simple but powerful. The pancyclic problem is intended to showcase the power this method offers to solve a wide range of 2-factorization problems. Indeed, these methods go a long way towards being able to produce arbitrary 2-factorizations with one or two cycles per factor.

Details DOI