A SAT+CAS Method for Enumerating Williamson Matrices of Even Order

AAAI Conferences

We present for the first time an exhaustive enumeration of Williamson matrices of even order n < 65. The search method relies on the novel SAT+CAS paradigm of coupling SAT solvers with computer algebra systems so as to take advantage of the advances made in both the field of satisfiability checking and the field of symbolic computation. Additionally, we use a programmatic SAT solver which allows conflict clauses to be learned programmatically, through a piece of code specifically tailored to the domain area. Prior to our work, Williamson matrices had only been enumerated for odd orders n < 60, so our work increases the bounds that Williamson matrices have been enumerated up to and provides the first enumeration of Williamson matrices of even order. Our results show that Williamson matrices of even order tend to be much more abundant than those of odd orders. In particular, Williamson matrices exist for every even order n < 65 but do not exist in orders 35, 47, 53, and 59.

Effective problem solving using SAT solvers

arXiv.org Artificial Intelligence

In this article we demonstrate how to solve a variety of problems and puzzles using the built-in SAT solver of the computer algebra system Maple. Once the problems have been encoded into Boolean logic, solutions can be found (or shown to not exist) automatically, without the need to implement any search algorithm. In particular, we describe how to solve the $n$-queens problem, how to generate and solve Sudoku puzzles, how to solve logic puzzles like the Einstein riddle, how to solve the 15-puzzle, how to solve the maximum clique problem, and finding Graeco-Latin squares.

Delineating Knowledge Domains in the Scientific Literature Using Visual Information

arXiv.org Machine Learning

Figures are an important channel for scientific communication, used to express complex ideas, models and data in ways that words cannot. However, this visual information is mostly ignored in analyses of the scientific literature. In this paper, we demonstrate the utility of using scientific figures as markers of knowledge domains in science, which can be used for classification, recommender systems, and studies of scientific information exchange. We encode sets of images into a visual signature, then use distances between these signatures to understand how patterns of visual communication compare with patterns of jargon and citation structures. We find that figures can be as effective for differentiating communities of practice as text or citation patterns. We then consider where these metrics disagree to understand how different disciplines use visualization to express ideas. Finally, we further consider how specific figure types propagate through the literature, suggesting a new mechanism for understanding the flow of ideas apart from conventional channels of text and citations. Our ultimate aim is to better leverage these information-dense objects to improve scientific communication across disciplinary boundaries.

Parameter Tuning for Self-optimizing Software at Scale

arXiv.org Artificial Intelligence

Efficiency of self-optimizing systems is heavily dependent on their optimization strategies, e.g., choosing exact or approximate solver. A choice of such a strategy, in turn, is influenced by numerous factors, such as re-optimization time, size of the problem, optimality constraints, etc. Exact solvers are domain-independent and can guarantee optimality but suffer from scaling, while approximate solvers offer a "good-enough" solution in exchange for a lack of generality and parameter-dependence. In this paper we discuss the trade-offs between exact and approximate optimizers for solving a quality-based software selection and hardware mapping problem from the scalability perspective. We show that even a simple heuristic can compete with thoroughly developed exact solvers under condition of an effective parameter tuning. Moreover, we discuss robustness of the obtained algorithm's configuration. Last but not least, we present a software product line for parameter tuning, which comprise the main features of this process and can serve as a platform for further research in the area of parameter tuning.

Production Ranking Systems: A Review

arXiv.org Machine Learning

The problem of ranking is a multi-billion dollar problem. In this paper we present an overview of several production quality ranking systems. We show that due to conflicting goals of employing the most effective machine learning models and responding to users in real time, ranking systems have evolved into a system of systems, where each subsystem can be viewed as a component layer. We view these layers as being data processing, representation learning, candidate selection and online inference. Each layer employs different algorithms and tools, with every end-to-end ranking system spanning multiple architectures. Our goal is to familiarize the general audience with a working knowledge of ranking at scale, the tools and algorithms employed and the challenges introduced by adopting a layered approach.