The SATCAS Method for Combinatorial Search with Applications to Best Matrices In this paper, we provide an overview of the SATCAS method that combines satisfiability checkers (SAT solvers) and computer algebra systems (CAS) to resolve combinatorial conjectures, and present new results visavis best matrices. The SATCAS method is a variant of the Davisunicode8211Putnamunicode8211Logemannunicode8211Loveland operatornameDPLL(T) architecture, where the T solver is replaced by a CAS. We describe how the SATCAS method has been previously used to resolve many open problems from graph theory, combinatorial design theory, and number theory, showing that the method has broad applications across a variety of fields. Additionally, we apply the method to construct the largest best matrices yet known and present new skew Hadamard matrices constructed from best matrices. We show the best matrix conjecture (that best matrices exist in all orders of the form r2r1) which was previously known to hold for rleq6 also holds for r7. We also confirmed the results of the exhaustive searches that have been previously completed for rleq6.

Lower Bounds Against Sparse Symmetric Functions of ACC Circuits: Expanding the Reach of SAT Algorithms. We continue the program of proving circuit lower bounds via circuit satisfiability algorithms. So far, this program has yielded several concrete results, proving that functions in textQuasiNP  textNTIMEn(log n)O(1) and textNEXP do not have small circuits from various circuit classes cal C, by showing that cal C admits nontrivial satisfiability andor SAT algorithms which beat exhaustive search by a minor amount.  this :62,paper, we present a new strong lower bound consequence of nontrivial SAT algorithm for a circuit class mathcal C. Say a symmetric Boolean function f(x_1,ldots,x_n) is sparse if it outputs 1 on O(1) values of sum_i x_i. We show that for every sparse f, and for all typical cal C, faster SAT algorithms for cal C circuits actually imply lower bounds against the circuit class f circ cal C, which may be stronger than cal C itself. In particular:  algorithms for :143,168,nksize cal Ccircuits running in 2nnk time (for all k) imply textNEXP does not have f circ cal Ccircuits of polynomial size.  algorithms for 2nepsilonsize cal Ccircuits running in 2nnepsilon time (for some epsilon u003e 0) imply textQuasiNP does not have f circ cal Ccircuits of polynomial size.  SAT algorithms from the :195,literature, one immediate corollary of our results is that textQuasiNP does not have textEMAJ circ textACC0 circ textTHR circuits of polynomial size, where textEMAJ is the exact majority function, improving previous lower bounds against textACC0 Williams JACMu002714 and textACC0 circ textTHR Williams STOCu002714, MurrayWilliams STOCu002718. This is the first nontrivial lower bound against such a circuit class.